COE2SI4: Data Structures, Algorithms, and
Discrete Mathematics
Calendar
Introduction to abstraction of procedures and data. Algorithms,
recursive and iterative implementations, analysis of
computational complexity. Abstract data
types. Arrays and structures, pointers to arrays.
Polynomial and sparse matrix abstract data types.
Stacks, queues, and lists. Trees, hashing, sorting, and
searching. Graphs and paths. Basic set theory, Boolean algebra,
combinatorics, elements of discrete probability
theory.
Objectives
Understanding of the ideas of abstraction of procedures and data
and analysis of computational complexity.
Handling of the fundamental
data types such as arrays, structures,
arrays of structures, lists, stacks, queues, trees and graphs.
Getting experience in using abstract data types
on a computer. Learning basic concepts
of discrete mathematics, elements of combinatorics,
and discrete probability theory.
Course Loading
three 1-hour lectures per week, one 2-hour tutorial per
week
Assessment
Assignments - 15%
Midterm - 35%
Final Exam - 50%
Textbook
-
C. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data
Structures in C,
Computer Science Press, 1993, ISBN 0-7167-8250-2.
- Reference: H. Schildt, C: The Complete Reference,
McGraw-Hill, ISBN 0-07-882101-0.
Lecture Notes/Viewgraphs (some 260 pages are available now)
-
postscript file
-
pdf file
Office hours (TA's)
-
John Lu (CRL/205, Fridays, 9:00-12:00 a.m.)
-
Marius Pesavento (CRL/205, Wednesdays, 10:30 a.m.-1:30 p.m.)
-
Scarlett Chan (CRL/205, Thursdays, 2:00-5:00 p.m.)
Office hours (instructor)
-
CRL/222, Fridays 9:00-12:00
-
Tutorials
-
Tutorial #1 (MS-Word (.doc) file).
-
Tutorial #2 (MS-Word (.doc) file).
-
Tutorial #3 (MS-Word (.doc) file).
-
Tutorial #4 (MS-Word (.doc) file).
-
Tutorial #5 (pdf file).
-
Tutorial #6 (pdf file).
-
Tutorial #7 (pdf file).
-
Tutorial #8 (pdf file).
Assignments
-
Assignment #1 as
ps-file
and
pdf-file
Please, submit this assignment to Dr. A.B. Gershman (CRL/222),
John Lu (CRL/205) or Marius Pesavento (CRL/205) no later than
October 3, Tuesday, 12:30 p.m. (preferably submit
your assignment to Dr. Gershman right after the Tuesday lecture,
Oct. 3).
The late submission penalty will
be 15%. No submission can be accepted later
than October 6.
The following materials must be submitted in a large envelope:
-
floppy disk containing your programs: C-codes and
executables. Please, identify yourself (name, ID) on the floppy disk.
-
your report including flow-chart (if requested),
printed listing of a C-code of each program,
and answers to theoretical questions (if requested).
Please, identify yourself (name, ID) in the first page of your report.
-
Assignment #2 as
ps-file
and
pdf-file
and
auxiliary text-file
Please, submit this assignment to Dr. A.B. Gershman (CRL/222),
John Lu (CRL/205) or Marius Pesavento (CRL/205) no later than
November 20, Monday, 11:30 a.m. (preferably submit
your assignment to Dr. Gershman right after the Monday lecture,
Nov. 20).
The late submission penalty will
be 15%. No submission can be accepted later
than November 23, 11:30 a.m.
The following materials must be submitted in a large envelope:
-
floppy disk containing your programs: C-codes and
executables. (You are NOT requested to
provide flow-charts!
Please, identify yourself (name, ID) on the floppy disk)
-
your report including
printed listing of a C-code of each program
and printed results
(Please, identify yourself (name, ID) in the first page of your report).
Midterm
-
Thursday, October 26, 9:30 a.m., JHE/264.
There will be several theoretical problems/questions
that should be solved/answered.
The material included in the midterm corresponds
to Chapters 1-5 of the lecture notes (pp. 1-180,
up to the end of the Chapter "Trees").
All problems given during the test are entirely
based on the coursware (slides). There will be NO
C-programming questions. You are not allowed to
use any material (lecture notes, book, or something else)
during the test.
Solutions to midterm problems
-
ps-file
and
pdf-file
Final Exam
-
There will be nine theoretical problems/questions
that should be solved/answered.
The exam covers evenly the course material.
All problems given during the test are entirely
based on the coursware (slides). There will be NO
C-programming questions. You are not allowed to
use any material (lecture notes, book, or something else)
during the test. There will be questions related to asymptotic notation
(order of growth), different
ADT's, stacks, queues, and lists, trees and graphs,
sorting and searching, and discrete probabilities.
Good luck!!!