COMS3136 Essential Data Structures in C/C++

Fall 2022

Course info

Essential Data Structures in C/C++ is an intermediate course covering the programming languages C and C++, and the concept of Data Structures including arrays, linked lists, trees, and graphs. It is a designed as a bridge class between an introductory programming class like ENGI1006 and advanced programming classes in the 4000s. After the two-course sequence of 1006 and 3136, students should feel comfortable with the programming requirements of any 4000 level class in the Computer Science department. As such, it is primarily intended for non computer science majors, though any student is welcome to attend.

In addition to C, C++, and Data Structures, this class will make heavy use of git and UNIX programming tools. Students will become comfortable working in a fully remote, public-cloud based linux machine with only a terminal and a text editor. These skills are often considered a diffentiator between a “programming student” and a “programmer”.

In terms of other courses, this class is a fusion of COMS3157 and COMS3134. It includes the C/C++ content from 3157, but without the systems programming, and it includes the essential data structures from 3134 without the more theoretical/esoteric data structures discussed therein.

No prior knowledge of C/C++ is required for this course.

Textbook

There is no required textbook for this course. However, here are some suggested reference materials:

Supplementary materials

Software

All coursework will be performed on cloc.cs.columbia.edu, on which all required software is preinstalled.

Attendance

You are expected to attend all lectures, either in-person or virtually. Any material covered in class or in a homework is fair game for exams. All courses will be available in real time on Zoom, and recorded for asynchronous viewing or review.

Academic Honesty

REQUIRED READING: ACADEMIC HONESTY POLICIES

School Policies

In addition to this policy, the CS department’s academic honesty policy applies to this course. Please revisit your school’s standards for academic integrity:

Schedule

Note that the following schedule is tentative. It will be updated as we go.

# Date Topic Note Deadline
1 T 9/6 Course overview 00 R 9/8 NOON: HW0 Part A due
2 R 9/8 Compiling & linking; Makefile 01 F 9/9: HW0 Part B due
3 T 9/13 Makefile; Binary number; Data types 02, HW1
4 R 9/15 Binary number; Data types; Expressions & statements
5 T 9/20 Automatic v. static variables; Process address space
6 R 9/22 Recursion; Selection sort 03, HW2 Su 9/25: lab1 due
7 T 9/27 Merge sort; HW2 code walk-through
8 R 9/29 Pointers & arrays 04
9 T 10/4 Pointers & arrays
10 R 10/6 Heap allocation; Pointer to pointer; Struct HW3 Su 10/9: lab2 due
11 T 10/11 Function pointer; Linked list I 05
12 R 10/13 Linked list II 06
13 T 10/18 Linked list II; Big-O notation
14 R 10/20 I/O 07, HW4
15 T 10/25 Introduction to C++ F 10/28: lab3 due
16 R 10/27 MyString class I 08
- T 11/1 Midterm Exam 09, HW5
- R 11/3 No Class - Cancelled
- T 11/8 No Class - University Holiday
17 R 11/10 MyString class II
18 T 11/15 Binary Search Tree I 10
19 R 11/17 Binary Search Tree II 11 F 11/18: lab4 due
20 T 11/22 Templates and STL I 12, HW6
- R 11/24 No Class - University Holiday
21 T 11/29 Templates and STL II
22 R 12/1 Graph I: Data Structure Overview 13 F 12/2: lab5 due
23 T 12/6 Graph II: DFS & BFS
24 R 12/8 Course wrap-up & review T 12/13: lab6 due
- TBD Final: Tuesday December 20, 7–10pm 829 Mudd