New Jersey Institute of Technology

Digital Commons @ NJIT

Computer Science Syllabi NJIT Syllabi

Fall 2020

CS 610-103: Data Structure & Algorithm

Alex Gerbessiotis

Follow this and additional works at: https://digitalcommons.njit.edu/cs-syllabi

Recommended Citation
Gerbessiotis, Alex, "CS 610-103: Data Structure & Algorithm" (2020). Computer Science Syllabi. 136.
https://digitalcommons.njit.edu/cs-syllabi/136

This Syllabus is brought to you for free and open access by the NJIT Syllabi at Digital Commons @ NJIT. It has
been accepted for inclusion in Computer Science Syllabi by an authorized administrator of Digital Commons @
NJIT. For more information, please contact [email protected].
 A. V. GERBESSIOTIS
CS610
Fall 2020 August 18, 2020
Course Syllabus: General Information
Page 1 Handout 1

1.1 CONTACT INFORMATION

Instructor: Alex Gerbessiotis E-mail: [email protected]
Office: GITC 4213, 4th floor Tel: (973)-596-3244
Contact Hours: Tue and Thu 4-5:20pm (Webex)
Contact Hours: Tue 1-2:20pm (NJIT;check web-page)
Assistant: TBA on WEB
Class Hours: 6:00-8:50pm
Web-Page: http://www.cs.njit.edu/∼alexg/courses/cs610/index.html
Web-Page: http://web.njit.edu/∼alexg/courses/cs610/index.html

1.2 COURSE ADMINISTRATION

CourseWork: 2 exams ; 4 Homeworks (HW) ; Programming project (aka PrP).
Points: 1000points=PrP(160)+Ex1(360)+ Ex2(360)+HW(120)
PrP: A programming project (PrP) with 2 options each one worth 160 points. A student may
submit one or two options in ONE archive per Handout 2 AND SUBMITTED VIA Canvas
BEFORE 12-o’clock ’noon’ of the date specified in the Calendar which is a Wednesday that
is not a class day! Turnitin will be activated in canvas.
HW, PS: Several problem sets (PS) will be periodically posted that would include problems with ac-
companying solutions. Homeworks will be given out. Submission through Canvas;on a
non-class Wednesday cycle. PSes are not for credit; HWs are for credit.
Exams: Dates in Course Calendar and on a class day starting at 6pm. Exam1 (120mn) is midterm.
Exam2 (120mn) is final. The two exams are on canvas and through ProctorU; you need to
create a ProctorU account early, at least three FULL weeks before the first exam, if you don’t
have one. Exam 1 and Exam 2 are closed everything and cumulative.
1.3 BASELINE COURSE SYLLABUS
Course: CS610. Data structures and algorithms.
Credits: 3 credits.
Prerequisites: (CS506 or CS241) and (CS505 or CS114).
Description: Intensive study of the fundamentals of data structures and algorithms. Presents the defini-
tions, representations, processing algorithms for data structures, general design and analysis
techniques for algorithms. Covers a broad variety of data structures, algorithms and their
applications including linked lists, various tree organizations, hash tables, strings, storage al-
location, algorithms for searching and sorting, and a selected collection of other algorithms.
Textbook: [Recommended, designated] Algorithm Design: Foundations, analysis, and internet exam-
ples. M. T. Goodrich and R. Tamassia. Wiley, 2001, ISBN 0-471-38365-1.
Referred to hereafter as GT.
 A. V. GERBESSIOTIS
CS610
Fall 2020 August 18, 2020
Course Syllabus: Outcomes and Topics
Page 2 Handout 1

Learning Outcomes:
1. Learn how and be able to understand and formulate the input-output relationship of computational
problems, and formulate the requirements, data and operations of abstract data types (ADT).
2. Learn how and be able to asymptotically compare functions using o, O, ω, Ω, Θ, and be able to solve
recurrences using the master, iteration/recursion tree, and the substitution methods.
3. Learn how and be able to describe, derive and determine, the asymptotic performance of algorithms for
computational problems and operations on elementary and more advanced data structures.
4. Learn how they operate and be able to understand fundamental algorithms and data-structures, and un-
derstand their characteristics for problems related to searching, sorting, selection, operations on num-
bers and polynmials and matrices and graphs. Be able to choose among a variety of similar ones based
on problem/program specification and requirements.
5. Learn how and be able to compose more complex algorithms using as building blocks the fundamental
algorithms introduced in class.
6. Learn how and be able to compose more complex algorithms using the algorithmic design techniques
introduced in class.
7. Learn how and be able to compose advanced data structures using as building blocks the elementary
data structures introduced in class.
8. Learn how and be able to implement in a high-level imperative language some of the algorithms and
data structures introduced in class in the form of a programming project of considerable complexity.
9. Learn how and be able to understand and possibly identify that some problems are complex and are not
susceptible to ’easy’ solutions. Learn how and be able to understand the benefits and complexities of
using randomness in computation.

Topics (with references to chapters of the designated textbook):

T1. Ch1,2.1-2.2,4.1-4.2,5.1-5.2: Introduction. Algorithm Analysis. Asymptotic notation. Sorting. Algo-
rithm Design Techniques. Elementary data structures.
T2. Ch1,5.2: Asymptotic growth of functions and Recurrence relations.
T3. Ch2.3,5,6.1-6.4: Graphs and their representation. Traversals. Union-find.
T4. Ch2.5-2.7: Hashing (by chaining and open-addressing). Google Example.
T5. Ch2.4,5.1,9.3: Heaps and Priority Queues. Greedy Method. Huffman codes.
T6. Ch4: QuickSort. Complexity of sorting. Linear-time sorting.
T7. Ch4: Selection; Order statistics
T8. Ch4.2,6,7: Graphs and their representation. Graph traversals. Strong connectivity. Topological sorting.
Shortest paths. Minimum cost spanning trees.
T8. Not in GT: Graphs and Web-page Ranking: Google’s PageRank, Kleinberg’s HITS algorithm.
T9. Ch5.2-5.3: Integer and Polynomials. Matrices. The WORD and BIT models.
T10. Ch3: Binary Search Trees and Balanced Binary Search trees.
T11. Ch3.3, 14.1.2: Search Trees of Bounded Depth (and Height)
T12. Ch9.1: String and Pattern matching algorithms (if time permits).
T13. Ch13.1-13.2: The theory of NP-completeness: P, NP, co-NP, NPC, NP-hard.
 A. V. GERBESSIOTIS
CS610
Fall 2020 August 18, 2020
Course Syllabus: Calendar
Page 3 Handout 1

1.4 CALENDAR

Fall 2020(Week starts on Tuesday)

Week Item Out Item In
W01 HW are Wed-Wed HW in before noon on a Wed
W02 HW1 out on 9/09
W03 HW1 in on 9/16
W04 HW2 out on 9/23
W05 HW3 out on 9/30 HW2 in on 9/30
W06 HW3 in on 10/7
W07
W08 FULLY ONLINE Ex1:Midterm ProctorU on class day
W09
W10 HW4 out on 11/4
W11
W12 HW4 in on 11/18
W13 Wed is NJIT Fri Thanksgiving is on 11/26
W14 PrP before noon on Wed 12/2
W15
W16 FULLY ONLINE Ex2:Final ProctorU on class day

Any modification/deviation from the calendar and its items will be done in consultation with the at-
tending a class students and be posted on the course web-page. It is imperative that students check
the course web-page regularly and frequently. Exceptions are as announced by the Provost’s Office.

1.5 COURSE POLICIES

OARS: If you need special accommodations, contact the Office of Accessibility Resources and Ser-
vices, KUPF 201, to discuss your specific needs. A Letter of Accommodation Eligibility from
OARS authorizing your accommodations will be required and should be received by us at least
two weeks plus two days before the first exam, if it also relates to exams.
MISSING: If you miss a class, you make up for lost time. No PrP extensions for any reason, medical or
otherwise; you have 3 months to submit it: submit EARLY. If you miss an exam you MUST
CONTACT the Dean of Students (DOS) within 2 working days from the day the reason for
the absence is lifted with all necessary documentation and email the instructor of your intent
and absence. The maximum accommodation period will be the number of missing days to the
exam date: it is imperative then that you contact DOS even before the 2 working day period
has expired if the accommodation period would be shorter. A makeup will be given in the
rarest of cases.
Devices: Power down and switch off (not just silence) mobile and other devices and place them in a
bag or backpack or on the floor, screen facing down. IF A STUDENT GETS CAUGHT
HAVING A DEVICE (on or off) ON HIM/HER, the exam receives a 0. DEVICES MUST
BE OFF and NOT ON YOU. For ProctorU exams ”ON YOU” means anywhere viewable
including at a distance of less than 6ft. A not completely powered down device of yours is
assumed to be ”ON YOU” independently of proximity.
 A. V. GERBESSIOTIS
CS610
Fall 2020 August 18, 2020
Course Syllabus: Course Policies
Page 4 Handout 1

1.5 COURSE POLICIES (continued)

Grading: For paper exams, if any, do not use pencils to write down your answers. If you do use a pencil
do not complain about grading after an exam. Scratch paper is forbidden unless explicitly
allowed in an online exam. Work submitted will be graded for conciseness and correctness;
be brief and to the point and write clearly. Material covered in class and appearing in the
relevant notes and chapters of the designated textbook can be used without proof. Everything
else requires a proof (justification) of solution. For PrP-grading see Handout 2 for details
(section Testing and Grading). On the sum of the grades of the options, a 0-60 grade is
accounted as 0; an over-60 grade is cut-off at 160 points. Over-160 points are excess points.
Grades: Check marks and report errors promptly. Resolve any issues WITHIN 2 CALENDAR
WEEKS and before the first Reading Day starting from the day an exam is returned/released,
or homework graded. For PrP or the Final exam, within 5 calendar days from the day grades
are posted on canvas or Banner, as applicable. Talk to the grader first, and then to the instruc-
tor (if different). The final grade is decided on a 0 to 1000 point scale. If you get less than
500 points in the class, expect an F. If you collect at least 500 points you should expect a C or
better. 850 points or more are usually needed for an A including robust programming work
but this threshold can be lower. (All these assuming no violation of the Collaboration policy.)
After letter grades are decided, excess points are then applied to determine if an upgrade by
one level (eg B to B+ ) is possible.
Incomplete: A grade of I(incomplete) is given in rare cases where work cannot be completed during the
semester due to documented long-term illness or absence (e.g. unexpected national guard
duty). A student needs to be in good standing (i.e. passing the course before the absence).
An email (in lieu of a written letter) with a timeline of what is needed to be done will be sent
to the student and the Department Chairperson. Not showing up in the final will probably get
you an F rather than an I.
Collaboration: Collaboration of any kind (in HW, Exams, PrP) is PROHIBITED. Students must turn
in work that has fully been composed and written by them and no-one else. Finding an
answer on the Internet, Web, or otherwise, or it is product of someone else’s work, or it
is common with another student submission, in the same or other section/course risks
punishment as outlined by the University. All parties of such interaction receive a 0 and
letter grade is lowered by one or two levels. The work you submit must be the result of
your own mental effort.
Email/SPAM: Use an NJIT email address or your email might not reach us. Send email to the designated
course email address per Handout 0 instructions!

The NJIT Academic Integrity (Honor) Code will be upheld; violations will be reported to the Dean of
Students (DOS). Read this handout carefully! .