CS1020 - Data Structures and Algorithms I (C++)


Overview: This module is the second part of a three-part series on introductory programming and problem solving by computing. It continues the introduction that begins in CS1010, and emphasises Object-Oriented Programming (OOP) with application to simple data structures. Topics include object-oriented problem modeling with objects, classes and methods, object-oriented problem formulation and solving, data structure implementation strageties, abstraction and encapsulation of data structures, object-oriented programming constructs, APIs and class libraries, exception handling, lists, linked lists, stacks, queues, hash tables and their algorithmic design, sorting and searching methods, recursive algorithms, and Big-O notation. This module is appropriate for FoE students.

Note: This introductory message will not be prominent the next time you visit this URL again. This behavior is normal. You can view it again by scrolling to the top of this page.

Course Registration

This is the first time Steven runs CS1020E.

As of Monday, 05 September 2016 morning (Week 05), I have 164 students, six less compared to S1 of last AY.
About ~100 are from ISE (pre-allocated) and the other ~70 are from other Engineering courses, Science, some Exchange students, and a few from various other faculties.

Useful information about CS1020E (see CS1020E in nusmods.com) in S1 AY 2016/2017:

  1. It will be Steven's first, although he has taught related modules like CS1102C (an old module like today's CS2020, in C++, no longer mounted), CS2020 (a combined CS1020+CS2010 accelerated module, in Java), and CS2010 (the next module after CS1020/CS1020E) before... There will be surely some hiccups, hopefully not that many/major, along the way... One very probable 'problem' is that Steven calibrates this module 'wrongly', i.e. 'too hard'... as he comes from higher level module background (e.g. CS2010, CS3233...) and also teaches hard algorithm module (CS4234) concurrently at the same time
  2. Teaching staffs:

    (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used very extensively in the second half of CS1020E under him.

    Teaching Assistants (TAs) who will help Steven run the Tutorial+Lab hybrid this semester are:

    1. Ivan Chew Teck Meng (full-time TA)
    2. Melvin Tan Jun Keong (UG),
    3. Ng Say-Yao Mark (UG),
    4. Le Xuan Manh (UG),
    5. Luo Pingyi (GAP),
    6. Abdelhak Bentaleb (GAP), and

    Their current Tutorial+Lab hybrid assignments, venue, and timings can be found here.

  3. Have you passed (or exempted from) CS1010 or its variants (especially CS1010E)?
    You have to...
  4. Are you still a freshman but somehow exempted from CS1010 or its variants (especially CS1010E) and have to take CS1020E sooner or later?
    Take CS1020E with Steven in S1 as CS1020E should be eligible for this :). Study under Steven who is known to run difficult module without worrying too much about your own grade.
    Update: 99% out of enrolled students are apparently 2nd year onwards so this recent news is probably irrelevant...


This is what you will learn if you take CS1020 in S1:

  • Part 1: Object-Oriented Programming (OOP) with C++:
    1. The Basics of C++ Language
    2. OOP Concepts: Encapsulation, Inheritance, Polymorphism, etc
    3. Useful Features in C++
  • Part 2: Abstract Data Types (ADTs) and Various Linear Data Structures (DSes):
    1. List/Stack/Queue/Deque ADTs
    2. Array/Vector
    3. (Single/Doubly) Linked List
  • Part 3: Recursive and Sorting Algorithms, with basic algorithm analysis:
    1. Recursion, and various application scenarios
    2. The simple Big-O algorithm analysis
    3. Sorting algorithms, and various application scenarios
  • Part 4: One More Non-Linear Data Structure:
    1. Hash Table with several Hashing algorithms
  • Throughought this module:
    1. Ideas about OOP, implemented in C++
    2. Various trade-offs situations
    3. Real-life problem solving skills
    4. Recursive thinking
    5. Proper implementation of data structures and algorithms in C++

Course Registration Additional FAQ

If you have any important questions regarding this module, email stevenhalim at gmail dot com. Relevant answers will be posted here to reach wider audiences.

Q: Will there be a practical exam/coding test for CS1020E?
A: Yes, there will be two Practical Exams (PEs) on two Friday nights. Additionally, there will be 9C7 (9 choose best-7) short take-home labs (that is, easier to get full marks there).
Q: Will this module be graded using Bell curve?
A: Yes, as the enrollment is much more than 100 students.
Q: I am from CS1010/other basic programming methodology modules that do not use C++, should I pick up C++ on my own during this June-early August holiday?
A: Yes, that is a good idea.
Q: What Integrated Development Environment (IDE) that we will use in CS1020E?
A: The choice of IDE is entirely up to you.
Q: Do I have to buy any textbook for this course?
A: Generally, no. My Competitive Programming book, the 3rd edition (actually for CS3233) can be a good book to have if you later want to take CS2010 and other advanced algorithm courses later. The answers for very few of my test questions may be inside that book. The problem is... I discuss over 1655 problems far more difficult than CS1020E level in that book and the next edition (CP4) with more challenging problems is in the pipeline... :D.
Q: Will the lectures be recorded as webcast?
A: Yes. But it cannot beat the live lectures.

Note: This course registration section will not be prominent from Week 02 onwards (after first lecture). This behavior is normal. You can view it again by scrolling to the top of this page.


Date News

Lesson Plan

Week Lecture
Mon 4-6pm
Cells with updated course material are highlighted with light blue color, past classes are highlighted with khaki color, current week is highlighted with light green color, future classes are not highlighted
08 Aug
Not started, but please revise
your CS1010(E)
08-12 Aug
L0 - Course Admin.pdf
L1 - Basic C++.pdf
PS: Public holiday on Tue, 9 Aug 16 (Singapore National Day); No CS1020E class is affected
15-19 Aug
L2 - OOP - Part I.pdf
Delivered by another lecturer: A/P Tan Sun Teck
Because Steven is in Russia for IOI 2016
22-26 Aug
L3 - OOP - Part II.pdf
29 Aug-02 Sep
L4 - Useful Features in C++.pdf
05-09 Sep
L5 - ADT.pdf (Abstract Data Type)
Start L6a - List ADT.pdf (Array, for Week06 Tut+Lab)
L5 - ComplexNumber.zip, L6 - List.zip, VA - Single Linked List
12-16 Sep
Lecture cancelled due to
Public holiday on Mon, 12 Sep 16
(Hari Raya Haji)

Make up lecture during Recess Week
Make up Lecture on Mon, 19 Sep 16, 4-6pm at LT15
is cancelled, just enjoy your recess week
PE1 debrief will be just a short one via mass email
Please prepare Midterm Test by yourself
26-30 Sep
PE1 debrief, Finish L6a (Linked List)
Then L6b - Linked List Variations.pdf
Discussion of past Midterm Test papers (DIY)
VA - Single Linked List, VA - Doubly Linked List, C++ STL list
03-07 Oct
L7a - Stack ADT.pdf and L7b - Queue ADT.pdf
L7 - Stack-Queue.zip
VA - Stack, VA - Queue, VA - Deque (optional)
Midterm Test: Up to Linked List (L6b)Stack/Queue/Deque (20%), T5, and Lab4
Date and Time: Saturday, 08 October 2016, 10am-12pm (effective 10.05-11.45am, 100m)
Venue: iCube Auditorium (capacity 348)
Open Book (now no restriction, this overrides the statement about helpsheet on L0 - Course Admin), just no electronic device
You can re-read the question paper here (solution file will be emailed to you to make it slightly harder for your junior to get the file)
10-14 Oct
L8 - Recursion.pdf
L8 - Recursion.zip
VA - Recursion
17-21 Oct
L9 - Analysis of Algorithms.pdf
L9 - useful_formulas.pdf
24-28 Oct
L10 - Sorting.pdf
VA - Sorting
PS: Public holiday on Sat, 29 Oct 16 (Deepavali); No CS1020E class is affected
31 Oct-
04 Nov
L11 - Hashing.pdf
VA - Hash Table
Last examinable material of CS1020E
07-11 Nov
L12 - WrappingUp.pdf
Wrapping Up, tie loose ends
Mix and Match
Deeper Problem Solving Skills (with past papers)
Final assessment preview
VisuAlgo Online Quiz preview
Short Preview of CS2010 (if you take it in the future)
Study Week
PE2 Debrief (via email)
Final Assessment Consultations (per request)
Final Assessment, Thursday, 24 November 2016 (Evening), Venue: MPSH5 (40%)

Tutorial+Lab Hybrid

The Tutorial and Laboratory sessions of CS1020E are combined into one hybrid session in the Laboratory setting.
The sessions contain mix of tutorial (theory) and laboratory (practical).
All slots are on Friday.
In the table below, you will see Tutorial+Lab hybrid time (in 24 hours format), venue (all in COM1), and TA name.

NoHour (on Friday)VenueTeaching Assistant
0110am-12pmCOM1-0114Ivan Chew Teck Meng
0212-14pmCOM1-0114Melvin Tan Jun Keong
0314-16pmCOM1-0114Ivan Chew Teck Meng
0416-18pmCOM1-0114Le Xuan Manh
0510am-12pmCOM1-0120Le Xuan Manh
0612-14pmCOM1-0120Luo Pingyi
0712-14pmCOM1-0113Mark Ng Say-Yao
0816-18pmCOM1-0120Abdelhak Bentaleb
1016-18pmCOM1-B108Melvin Tan Jun Keong