Title Image

CSCI2100/ESTR2102 Data Structures - CUHK Course Review

Term Taken: 2019 Spring

Instructor (Class A): Prof. Irwin King Kuo Ching

Grading Scheme

  • Written Assignments (5%)
  • Programming Assignments (20%)
  • Written Midterm Exam (20%)
  • Programming Midterm Exam (35%)
  • Written Final Exam (20%)

Textbook

Data Structures and Algorithm Analysis in C (2nd Edition), Mark Weiss, 1997.

Topics Covered

  • Big O, Omega, Theta Notation.
  • Linked List.
  • Stack.
  • Queue.
  • Tree: Binary Search Tree, AVL Tree, B-Tree, Trie.
  • Heap.
  • Hash: Separate Chaining, Linear/Quadratic Probing.
  • Bubble Sort, Insertion Sort, Selection Sort.
  • Merge Sort, Quick Sort, Shell Sort, Bucket Sort.
  • Graph: Topological Sort, Breadth-First Search, Depth-First Search.
  • Dijkstra’s Shortest Path Algorithm.
  • Minimum Spanning Tree: Prim’s Algorithm, Kruskal’s Algorithm.
  • Network (Maximum) Flow.

Additional Materials for ESTR:

  • Disjoint Sets.
  • Quick Select.
  • Dynamic Programming.
  • String Matching Automata (KMP Algorithm).
  • Bellman-Ford Shortest Path Algorithm, Min Cut Problem.
  • (Brief Introduction to) Traveling Salesperson Problem.
  • Computational Geometry: Convex Hull Problem, Quad-tree.

Review

This is a required course for CS, CE, IE, SEEM, AIST, and FTEC majors. Thus, it is usually split into many different sections. This article is about section A, taught by Prof. Irwin King.


Since data structures are the basic building blocks of computer science and programming, it is extremely important to MASTER this course.


The materials themselves weren’t difficult, and the data structures covered were pretty straightforward. However, this course was quite challenging because it required us to master both the abstract concepts as well as the actual implementation using the C programming language. Prof. King covered only the high level descriptions and operations of the data structures, so we had to spend a LOT of time coding the data structures to turn in the homework. Thus, in my opinion, this course kind of serves as a filter for CS students, you will become a genuine CS™ programmer after taking this course.


Programming assignments were released every two weeks. Each programming assignment consisted of three LeetCode-like problems with increasing difficulties. ESTR students were asked to solve all three problems while the last problem served as a bonus for regular students. We had to submit each problem through a PC2 system (similar to ACM competitions), so submission time was also a grading factor. I often got heart attacks before each submission session.


The written assignments were quite easy, yet it also took plenty of time because we had to illustrate each step of certain data structure operations by drawing, drawing and drawing. However, as time-consuming as they were, each written assignment added up only 1% of the final score, and the grading scheme was pretty…innovative. That is, for each written assignment, you get a full 1% if you “work hard”, otherwise you get 0%. There were no explicit guidelines but if you show each step clearly, you will very likely get a solid 1%. At least for me it worked like that.


The midterm exam and final exam had very similar formats and were pretty easy, you were asked to demonstrate the steps of certain operations (like in the homework), show the time/space complexity of some operations, design some simple algorithms, etc. Since the final exams had been pretty much the same for over 5 years, doing past-paper is 11/10 recommended.


Furthermore, because most people got similar scores for the midterm and final exams, the programming midterm was what made a difference. The programming midterm was a 3-hour mini-contest on a lovely Friday night, we were given 7 LeetCode-like programming problems similar to the programming assignments. They were intentionally designed to be challenging, so the class solved only around 3 problems on average. The final score would be curved according to the rank and the top students would receive prizes at the end of the semester. I consider the best way to prepare for the programming midterm is to grind LeetCode problems, since the last couple problems came directly from LeetCode Medium/Hards for this year. Also, since the programming midterm is open-book & open-note, printing C implementations of ALL data structures covered in class is a MUST!!! (Make sure the code in your notes is 100% correct, so you don’t have to waste your time debugging it during the exam.)


You will probably spend around 5-10 hours on average each week if you plan to master (or get an A in) this course, but it is 100% worth since this course is a stepping stone to all other fields in CS, not to mention Big-N tech companies do data structure and algorithms interviews for their hiring process.

I’ll Give You All I Have Here

C Implementations of Common Data Structures

Solutions to the Programming Assignment Problem Sets

My Cheatsheet for Programming Midterm

(Some implementations are pretty lame I know. So make your own cheat sheet!)

Past Programming Midterm

I happen to know some problems in programming midterms of past years.


(Notice that the first problem of each programming midterm is easy as heck, if you cannot solve a single problem, you might as well re-ponder the meanings of your life.)

2014
  1. Check if a string is palindrome.
  2. LeetCode problem 169.
  3. Design a Max Heap supporting the following operations: find-max, insert, delete-max, and change-max (change the value of the maximum element).
  4. Given the pre-order and in-order traversals of a binary tree, return the leaf nodes of this binary tree.
  5. Josephus problem: Given n people and the execution gap m, return the execution sequence.
  6. LeetCode problem 155.
  7. Given a dictionary containing several words. Your task is to answer queries asking whether a single word occurs in the dictionary.
  8. Determine whether a permutation can be generated by using two stacks.
2016

I don’t have the exact problem set for this year, so some problem descriptions may seem incomplete.

  1. ? (Probably something very simple, which isn’t worth mentioning.)
  2. Print a pyramid of numbers (?)
  3. Given a sequence of parentheses, determine whether it is valid. (That is whether each ( is matched with a ).)
  4. Similar to 2014 problem 5.
  5. Color of balloon. (String hashing for strings, representing each color. Similar to 2014 problem 7.)
  6. Given the pre-order and in-order of a binary tree, output the level-order traversal (breadth-first search).
  7. Receiving input from a number stream, return the median of the stream anywhere in the middle of the stream.
2019
  1. Given a sequence of integers, return the difference between the sum of all odd numbers and the sum of all even numbers.
  2. Given a playlist of length m with the initial song labels as 1,2,3,...,m, two operations are allowed: PLAY and REMOVE. The PLAY operation plays the current song in the playlist and then places it to the back of the playlist. The REMOVE operation removes the currently first song from the playlist and never plays it again. Return the songs being played according to the given operation sequences.
  3. Evaluate prefix expressions with operators +, -, *, / for positive integers. Return “division by zero” you encounter a zero divisor.
  4. LeetCode problem 378.
  5. LeetCode problem 3.
  6. LeetCode problem 124.
  7. LeetCode problem 1000.

(Seems like the TAs went full LeetCode this year…)


More CUHK Course Reviews