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.
There is no required textbook for this course. However, here are some suggested reference materials:
All coursework will be performed on cloc.cs.columbia.edu, on which all required software is preinstalled.
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.
REQUIRED READING: ACADEMIC HONESTY 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:
Note that the following schedule is tentative. It will be updated as we go.
| # | Date | Topic | Note | Deadline |
|---|---|---|---|---|
| 1 | T 9/3 | Course overview | 00 | R 9/5 NOON: HW0 Part A due |
| 2 | R 9/5 | Compiling & linking; Makefile | 01 | F 9/6: HW0 Part B due |
| 3 | T 9/10 | Makefile; Binary number; Data types | 02, HW1 | |
| 4 | R 9/12 | Binary number; Data types; Expressions & statements | ||
| 5 | T 9/17 | Automatic v. static variables; Process address space | ||
| 6 | R 9/19 | Arrays; Recursion; Intro to Big-O | 03, HW2 | Su 9/22: lab1 due |
| 7 | T 9/24 | More recursion; Selection Sort; More Big-O; | ||
| - | R 9/26 | No Class | ||
| 8 | T 10/1 | Merge Sort; Pointers & arrays | 04 | |
| 9 | R 10/3 | Heap allocation; Pointer to pointer; Struct | HW3 | |
| 10 | T 10/8 | Struct; Function pointer; Linked list I | 05 | |
| - | R 10/10 | No Class | ||
| 11 | T 10/15 | Linked list I | 06, HW4 | T 10/15: lab2 due |
| 12 | R 10/17 | Linked list II | ||
| 13 | T 10/22 | Linked List; More Big-O | ||
| 14 | R 10/24 | I/O | 7 | |
| - | T 10/29 | Midterm | ||
| 15 | R 10/31 | Introduction to C++ | 8 | Su 11/3: lab3 due |
| - | T 11/5 | No Class - University Holiday | ||
| 16 | R 11/7 | MyString class I | 9, HW5 | |
| 17 | T 11/12 | MyString class II | ||
| 18 | R 11/14 | Binary Search Tree I | 10 | |
| 19 | T 11/19 | Binary Search Tree II | 11 | T 11/19: lab4 due |
| 20 | R 11/21 | Templates and STL I | 12, HW6 | |
| 21 | T 11/26 | Templates and STL II | ||
| - | R 11/28 | No Class - University Holiday | ||
| 22 | T 12/3 | Graph I: Data Structure Overview | 13 | F 12/6: lab5 due |
| 23 | R 12/5 | Graph II: DFS & BFS, Course review | F 12/13: lab6 due | |
| - | T 12/17 | Final: 7–10pm TBD |