Data Structures and Algorithms (NYU Paris, Spring 2021)

The design and analysis of efficient data structures is a vital subject in computing and is part of the curriculum of every computer science and computer engineering student. In this course, we will learn how to model computational problems. We will cover the most important algorithms, algorithmic paradigms and data structures used to solve those problems. We will discuss efficiency and scalability.

More specifically, the course will cover topics such as object oriented programming, as well as Sorting and Trees, Hashing, Number theoretic algorithms including RSA encryption, Graphs and Shortest paths and the notion of NP-Completeness.

The students will get the opportunity to program the algorithms that are discussed during the lectures in Java.

The class will follow the structure 

1. Lectures (introduction of the new material that will be needed during the lab sessions and for the assignments)

2. Programming (lab) sessions, (you have the opportunity to apply what you have learned during the lecture, and you can ask all the questions you want to make sure you understand everything before the assignement)

3. Assignments (You are given a new problem and you are evaluated on your ability to use the course material to solve this new problem)

Schedule and Classroom

Lecture: Tuesday/Thursday, 12.30pm – 1.45pm (Paris time), Room 410
Recitations: Tuesday 2.15pm – 3.45pm (Paris time). Room 410
Office hour: Thursday 2.15pm – 3.45pm (Paris time)

 

Assignments policy

Except if explicitely stated otherwise, assignments are due at the beginning of each class.

 

Current (temporary) version of the notes:   Lecture notes

Practice (theory) Questions for each exam can be found by clicking on those exams below

Exam : 60% of the grade (30% midterm, 30% final)


Assignments : 30 % of the grade (Tentative schedule below)

 Final Project : 10 % of the grade (Tentative schedule below)

 

The Github page for the class will be hosted at https://github.com/acosse/DataStructures2021 and will be used for the lab and the assignments. You can also click on each “Lab” in the schedule below and this will re-direct you to the github page.

Tentative schedule:

Legend: Lab sessions are in green, Homeworks are in red (right side of the table), dates related to the project are in orange.

Week # date Topic Assignements
Week 1 01/26, 01/28 Reminders/Intro to Java, Elementary programming
including loops, strings, arrays, objects, classes,… Lab 1 (Setting up Java, git,..)
Slides
Week 2 02/02, 02/04 Object Oriented Programming and Design, Part I, Lab 2
Slides, Solution Ex1.1., Solution Ex1.2., Solution Ex1.3. 		Assign. 1
Week 3 02/09, 02/11 Object Oriented Programming and Design Part II
including inheritance and Abstract classes, Lab 3
Slides Inheritance, Slides arrays , Solutions Exercise 1.1 and 1.3 		Assign. 1 due,
Week 4 02/16, 02/18 Fundamental data structures Multidimensional arrays, Linked Lists,
Numerics, integers, RSA encryption, Slides, Lab 4
Solution Ex. 1.1, Ex. 1.7 (with Object) 		Assignment 2
Week 5 02/23, 02/25 Algorithm analysis including Asymptotic Analysis and the “Big Oh” notation
Slides
Assign.2 due
Week 6 03/02, 03/04 Recursion, Slides, Lab 5, Solutions exercises 1.1, 1.4 and 1.10
Week 7 03/09, 03/11 Stacks, Queues and Deques (Possibly List ADT), Slides Lab 6  

Week 8 03/16, 03/18 Trees Part I including general and Binary Trees,
Tree Traversal algorithms,.. Slides Part I , Slides Part II, Lab 7, Solutions
Week 9 03/23, 03/25 Trees Part II (including Search Trees, Balanced Search Trees)
Slides 1, Slides 2 , Slides 3, Lab 8
Week 10 03/30, 04/01 Priority queues, Heaps, Maps, Hash Tables Slides Priority Queues, Slides Maps,
Slides Hash Table (Part II), Lab 10
Week 11 04/06, 04/08 Sorting Part I, Lab 11
Week 12 04/13, 04/15 Sorting part II, Lab 12
Week 13 04/20, 04/22 Graph Algorithms including BFS, DFS, topological Sort,
Min Spanning trees, Max Flow,.. Lab 13		 Assignment 3
Week 14 04/27, 04/29 Advanced Topics including Dynamic Programming, Linear Programming,
Approximation and Randomized Algorithms,…
Week 15 05/04, 05/06 Revisions (link to Lab) Element iterator demo, Position iterator demo
Tree demo 		 

 

Lab Sessions and programming policy

The lab sessions will require you to do some programming.

Downloading and getting started with Java.