Queen's School of Computing CISC-235* - Winter 2017 Title and Photo Table

CISC-235*

Data Structures

Winter 2017


 

image by Gunnar Bothner-By, used under Creative Commons licence https://creativecommons.org/licenses/by/2.0/

Internal LinksAnnouncements

Personnel

Course Information

Schedule

Course Plan and Record

Assignments

Practice Problems

Recommended Readings

Sample Tests

Academic Integrity in CISC 235

Change Log


External_Links
External Links
Queen's School of Computing
Computing Students' Association
Class Photo Gallery
Learning - Your First Job (Paper by Dr. R. Leamnson) - ESSENTIAL READING
Academic Integrity Statement from Faculty of Arts and Science






Announcements

Announcements
Date Subject Text


Return to top



Personnel

Personnel
Instructor
Dr. Robin W. Dawes
Robin Dawes
Goodwin 537 
dawes AT cs DOT queensu DOT ca
http://sites.cs.queensu.ca/dawes/
533-6061 (but e-mail is a much better idea)
Office Hours: Until further notice, my office hours will be :
    Monday 2:00 - 4:00
    Tuesday 1:30 - 3:30

TAs
Name
Email  
Office Hours
Picture

Andre Foote
12atrf
Friday
1:00 - 2:00
Goodwin 241

Chris Givelas
13cmg9
Tuesday
2:00 - 3:00
Goodwin 248

Hassan Hanino
13hah2
Wednesday
3:30 - 4:30
Goodwin 241

Xiao Li
13xl18


Ashiqur Rahman
rahman@cs.queensu.ca
Monday
4:00 - 5:00
Goodwin 624

Winker Xiao
13yjx Monday
11:30 - 12:30
Goodwin 241




Return to top



Course Information

CISC-235 Course Information
Calendar Description
Design and implementation of advanced data structures and related algorithms, including correctness and complexity analysis. Efficient implementation of lists, sets, dictionaries, priority queues, trees, graphs, and networks using arrays, hash tables, heaps, and hierarchical linked structures. String and graph problems, such as string matching and shortest path. External storage and input-output complexity.
Text
Introduction to Algorithms, Third Edition, Cormen, Lieserson, Rivest, Stein
Syllabus
pretty much what the calendar says
Marking Scheme
4 Assignments - lowest counts 4%, the other three count 8%                            28%

4 Tests - lowest counts 12%, the other three count 20%                                    72%

There are no make-up tests in CISC-235.  If you miss a test due to valid extenuating circumstances (which do not include social activities or family gatherings)  I will revise your marking scheme.

You must have an overall passing grade on the tests (ie at least 36% out of the possible 72%) in order to pass the course.  

Students with special needs are responsible for contacting the instructor at least a week before each test.  Please see the Queen's Disability Services page for students for more information.






Return to top



Schedule

Schedule_Table
Class Schedule




Monday 8:30 - 9:20
Biosciences Auditorium
Tuesday 10:30 - 11:20 Biosciences Auditorium
Thursday 9:30 - 10:20 Biosciences Auditorium

Assignment and Test Schedule


Date
Location
Test 1
January 31
Biosciences Auditorium
Test 2 March 2
Biosciences Auditorium
Test 3 March 23
Biosciences Auditorium
Test 4 April 6
Biosciences Auditorium
Assignment 1
January 29

Assignment 2
February 26

Assignment 3
March 19

Assignment 4
April 9




Return to top



Course Plan and Record

Record Table
Week 1
Complexity Analysis
Monday, January 9
Plan: What's It All About?
20170109.pdf
Tuesday, January 10
Plan: This is getting ...
Thursday, January 12
Plan: ... quite complex
20170110+12
Week 2
Stacks and Queues
Monday, January 16
Plan: Example of Theta Classification
Tuesday, January 17
Plan: Stacks
Thursday, January 19
Plan: More Stacks
20170116+17+19
Week 3
Binary Search Trees
Monday, January 23
Plan: Intro to Trees
Tuesday, January 24
Plan: More Trees
Thursday, January 26
Assignment 1 due on January 29

Plan: Binary trees and Binary Search Trees
20170123+24+26
Week 4
Red-Black Trees
Monday, January 30
Plan:
Tuesday, January 31
TEST 1 (Complexity, Stacks, Binary Trees)
Solutions
Thursday, February 2
Plan:
Insert and Delete for BST Structure
20170130+0202
Week 5
Hashing
Monday, February 6
Plan: Red ...
Tuesday, February 7
Plan: Black ...
Thursday, February 9
Plan: Trees!
Notes for the week
Week 6
More Hashing
Monday, February 13
Plan: The End ...
Tuesday, February 14
Plan: ... of Red Black Trees
Notes for Monday and Tuesday
Thursday, February 16
Assignment 2 due on February 26
Plan: Notes for Thursday (hashing)
*** Reading Week ***
Week 7
B-Trees
Monday, February 27
Plan: More Hashing
Notes for Feb 27
Tuesday, February 28
Plan: Double Hashing
Notes for Feb 28
Thursday, March 2
TEST 2 (Red-Black Trees, Hashing)
Solutions
Week 8
Heaps
Monday, March 6
Plan: Choosing a Hashing Function, and Hashing Strings
Notes for March 6
Tuesday, March 7
Plan: Queues and Priority Queues
Thursday, March 9
Plan: The Max-Heap Structure
Notes for March 7 and 9
Week 9
Graphs
Monday, March 13
Plan: Heaps ...
Tuesday, March 14
Plan: ... and heaps ...
Thursday, March 16
Assignment 3 due on March 19
Plan: of Heaps
Notes for the full week
Week 10
MST
Monday, March 20
Plan: Graphs
Notes for March 20
Tuesday, March 21
Plan: BFS
Notes for March 21
Thursday, March 23
TEST 3 (Hashing, Priority Queues, Heaps, Graphs)
Solutions
Week 11
MST Algorithms and
Dijkstra's Algorithm
Monday, March 27
Plan: Prim ...
Notes for March 27
Tuesday, March 28
Plan:
Thursday, March 30
Plan:  The End of Prim
Notes for March 28 and March 30
Week 12
Bloom Filters

Monday, April 3
Plan: Dijkstra's Algorithm
Notes for April 3
Tuesday, April 4
Plan: Wrap-up
Thursday, April 6
Assignment 4 due on April 9

TEST 4
(BFS, DFS, MST Algorithms, Dijkstra's Algorithm)
Solutions


Return to top



Assignments

CISC-235 Assignments

Due Week
Assignment Instructions
Marking Scheme
End of Week 3/Beginning of Week 4 "All My Life I Have Been Searching" --- Bertrand Russell
Marking guide for Assignment 1
End of Reading Week "Trees are poems that the earth writes upon the sky" --- Kahlil Gibran
Marking guide for Assignment 2
11:59 PM, March 19
"Hash - There is no definition for this word - nobody knows what it is" --- Ambrose Bierce

Text file for use in Assignment 3
Marking guide for Assignment 3
11:59 PM, April 9
"The best time to plant a tree is 20 years ago; the second best time is today" --- Anonymous
Marking guide for Assignment 4



Return to top



Practice Problems

Practice Problems
Source
Exercises
http://www.cs.wustl.edu/~sg/CS241_FL99/hw1-practice.html 2, 3, 4
http://tinyurl.com/6pkjjdu 3, 4, 5, 6, 8, 9, 13, 14
http://tinyurl.com/82sr5p5 1, 2, 3, 4, 5
Cormen, Leiserson, Rivest, Stein, Chapter 6, Exercise Set 6.1
1, 3, 4, 5, 6, 7
CLRS, Chapter 6, Problems
Problem 6-2
CLRS, Chapter 11, Exercise Set 11.2
2, 3
CLRS, Chapter 11, Exercise Set 11.4
1
CLRS, Chapter 22, Exercise Set 22.1
1, 2, 3, 5
CLRS, Chapter 22, Exercise Set 22.2
4, 5, 6, 7
CLRS, Chapter 22, Exercise Set 22.3
11, 12
(for these, use our definition of the DFS algorithm - much simpler)
CLRS, Chapter 22, Problems
Problem 22-1
CLRS, Chapter 23, Exercise Set 23.1
1, 5, 10
CLRS, Chapter 23, Exercise Set 23.2
2























Return to top



Recommended Readings

Recommended Readings
Source
Section
Comments
Learning (Your First Job)
All
Essential reading for all students
Computer Science For Fun Any purely recreational



Algorithms and Data Structures (Wirth) Any - this book is an excellent resource for anyone studying data structures. The link to the free PDF version is on Line 6 under "Oberon Books"



The Art of Computer Programming (Knuth)

This is just a link to the Wikipedia page - the books themselves are available from Amazon (and "other sources").



Introduction to Algorithms (CLRS) 2.2
CLRS 2.3.2
CLRS 3.1
https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29
stacks
CLRS 10.1 stacks
http://www.c4learn.com/data-structure/c-program-stack-convert-decimal-to-binary/
example of using a stack
CLRS
10.4

CLRS
12.1

CLRS 12.2

CLRS 12.3

CLRS
13.1

CLRS
13.2

CLRS
13.3

CLRS
Problem 13-3 (Page 333)

The Interwebs
http://en.wikipedia.org/wiki/AVL_tree

CLRS
11.2

CLRS
11.3

CLRS
11.4

CLRS
6.1

CLRS
6.2

CLRS
6.3

CLRS
6.4

CLRS
6.5

CLRS
22.1

CLRS
22.1

CLRS
22.3

CLRS
22.4

CLRS
23.1

CLRS
23.2

CLRS
24.3

Wikipedia
http://en.wikipedia.org/wiki/Trie

Wikipedia
http://en.wikipedia.org/wiki/Bloom_filter

Numberphile
https://curiosity.com/videos/rsa-129-numberphile-numberphile/
Numberphile videos are always good - this one is about RSA cryptography
Buzzfeed - Python Dicts and hashing https://www.buzzfeed.com/andrewkelleher/deep-exploration-into-python-lets-review-the-dict-module?utm_term=.hxLOd7l1m2#.vjVykGAeRr this link provided by a past CISC-235 student
Atlantic - From Aristotle to Computers https://www.theatlantic.com/technology/archive/2017/03/aristotle-computer/518697/


Return to top



Sample Tests

CISC-235 Sample Tests
Test 1 Test 1 from 2016
Solutions
Test 2 Test 2 from 2016
Solutions
Test 3 Test 3 from 2015
- Question 5 deals with material we have not covered yet - we will start this topic on Monday
Solutions
Test 4 Test 4 from 2016
- Question 4 deals with a data structure that we have not covered this year
Solutions


Return to top



Academic Integrity in CISC 235

CISC-235 Academic Integrity Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 on the Arts and Science website) and from the instructor of this course.

Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification. Falsification includes attempting to obtain, or accepting, a grade that is not solely and completely based on the graded work as submitted. 

In CISC 235, academic integrity means that the work you hand in as your own (tests and assignments) really is your own. You may ask other people for general help in the course -- by which I mean general explanations and help with practice problems that are not being handed in. You may talk in general terms with other students about marked assignments, as in discussing strategies ("how are you handling the case where the list is empty?") or requirements ("are we supposed to print out all the data or just the average?"). You may not share code or even pseudo-code with anyone else.


CISC-235 has a zero-tolerance policy regarding departures from academic integrity.  There will be no exceptions.

Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university. 

Each student in CISC-235 is required to confirm that they have read this statement on academic integrity and that they understand the consequences of any departure from academic integrity.   Your assignments and tests will not be evaluated unless you complete this confirmation through onQ.


The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.





Return to top



Change Log

Change Log
Date Log Entry


170106 Website live
170108 Date of Test 1 changed to 170131
170110 Link to free PDF of Wirth's book "Algorithms and Data Structures" added to "Recommended Readings"
170110 Link to Wikipedia page for Donald Knuth's "The Art of Computer Programming" added to "Recommended Readings"
170115 Complete notes for Week 1 posted
170117 Assignment 1 posted
170118 TA contact information posted
170118 Sample Test 1 posted
170122 Complete notes for Week 2 posted
170124 Marking guide for Assignment 1 posted
170124 Broken link in "Course Record" repaired
170124 Office hours no longer on demand, now at fixed times
170126 Solutions for last year's Test 1 posted
170127 Complete notes for Week 3 posted
170205 Complete notes for Week 4 posted
170205 Solutions for Test 1 posted
170205 Assignment 2 posted
170210 Office hours for TAs updated
170212 Complete notes for Week 5 posted (including all pseudo-code needed for Assignment 2)
170215 Link to Numberphile video on cryptography added to Recommended Readings
170216 Sample Test 2 posted (solutions also posted)
170216 Office Hours for TAs updated
170220 Final notes on Red-Black Trees posted
170223 First notes on Hashing posted
170223 Office Hours for TAs updated
170223 Updated due date for Assignment 2 as announced in class
170224 Marking guide for Assignment 2 posted
170227 Notes on Quadratic Probing posted
170309
Assignment 3 posted
170310 Final notes on Hashing posted
170310 First notes on Priority Queues posted
170310 Link to Buzzfeed article on hashing added to Recommended Readings
170311 Link to data file for Assignment 3 repaired
170314 Marking guide for Assignment 3 posted
170314 Sample Test 3 posted
170315 Record Table updated
170315 Schedule Table updated
170319 Final notes on Priority Queues, Heaps and Heapsort posted
170319 Solutions for Sample Test 3 posted
170320 Link to Atlantic article on the origins of computing added to Recommended Readings
170321 Notes for March 20 posted
170321 Notes for March 21 posted
170326 Assignment 4 posted
170327 Notes for March 27 posted
170328 Sample Test 4 posted
170403 Link to Sample Test 4 fixed
170403 Final Notes on Prim's Algorithm posted
170404 Notes for April 3 posted
170406 Solutions for Test 2 and Test 3 uploaded
170424 Solutions for Test 4 uploaded


Return to top