Queen's School of Computing CISC-235* - Fall 2018 Title and Photo Table

CISC-235*

Data Structures

Fall 2018


 
A glass-walled building reflects other buildings

Urgent Notices
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
Queen's Academic Integrity Page






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 speaking to me in person is a much better idea)
Office Hours:

Monday 1:30 - 2:30
Tuesday 3:30 - 4:30
Wednesday not available
Thursday 2:30 - 4:30
Friday 9:30 - 10:30

TA
Name
Email  
Office Hours
Picture

Katherine Beaulieu






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 for your assignments to be included in your final grade.

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






Return to top



Schedule

Schedule_Table
Class Schedule




Monday 11:30 - 12:30
Jeffery 126
Tuesday 1:30 - 2:30
Jeffery 126
Thursday 12:30 - 1:30
Jeffery 126

Assignment and Test Schedule


Date
Location
Test 1
September 24, 2018
Test 2 October 15, 2018
Test 3 November 12, 2018
Test 4 November 29, 2018
Assignment 1


Assignment 2


Assignment 3


Assignment 4





Return to top



Course Plan and Record

Record Table

Week 1

Thursday September 6
Plan:
- Introduction
Notes:
No Implementation without Representation
Week 2
Monday September 10
Plan:
  - Complexity Analysis
Tuesday September 11
Plan:
  - Complexity Analysis
Thursday September 13
Plan:
  - Testing a Hypothesis
Notes:
Big O, Omega and Theta
Week 3
Monday September 17
Plan:
  - Stacks and Queues

Notes: Finishing Complexity Analysis
Tuesday September 18
Plan: 
  - Stacks and Queues

Notes: How does this stack up?
Thursday September 20
Plan:
  - Binary Search Trees
Week 4
Monday September 24
Plan:
TEST 1 (Complexity, Stacks, Queues)
Tuesday September 25
Plan:
 - Binary Search Trees
Thursday September 27
Plan:
  - Binary Search Trees
Week 5
Monday October 1
Plan:
 - Red-Black Trees
Tuesday October 2
Plan:
  - Red-Black Trees
Thursday October 4
Plan:
 
- Red-Black Trees
Week 6
Monday October 8
Plan:
THANKSGIVING
Tuesday October 9
Plan:
 - Hashing
Thursday October 11
Plan:
  - Hashing
Week 7
Monday October 15
Plan:
TEST 2 (Binary Search Trees, Red-Black Trees)
Tuesday October 16
Plan:
  - Hashing
Thursday October 18
Plan:
 
- Hashing
Week 8
Monday October 22
Plan:
 - Hashing
Tuesday October 23
Plan:
 - Priority Queues
Thursday October 25
FALL BREAK
Week 9

Monday October 29
Plan:
  - Heaps
Tuesday October 30
Plan:
 - Heaps
Thursday November 1
Plan: 
 - Heaps
Week 10
Monday November 5
Plan:
 - Introduction to Graphs
Tuesday November 6
Plan:
 - DFS
Thursday November 8
Plan:
- Prim
Week 11
Monday November 12
Plan:
TEST 3 (Hashing and Heaps)
Tuesday November 13
Plan:
 - Prim
Thursday November 15
Plan:
 - Prim
Week 12
Monday November 19
Plan:
 - Prim
Tuesday November 20
Plan:
 - Kruskal
Thursday November 22
Plan:
 - Kruskal
Week 13
Monday November 26
Plan:
 - Dijkstra
Tuesday November 27
Plan:
- It's a Mystery
Thursday November 29
Plan:
TEST 4 (Graph Theory)





Return to top



Assignments

CISC-235 Assignments

Due Date
Assignment Instructions
Marking Scheme















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)
The four volumes of TAOCP will teach you more about Computer Science than any other source.  Knuth is a monster.
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 2018W

This test took place slightly later than ours so it covers more material.  There will be no questions on binary trees on our test.
Solutions and Marking Guide
Test 2

Test 3

Test 4



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).

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.

Actions which contravene the regulations on academic integrity carry sanctions that include but are not limited to

  • a warning
  • loss of grades on an assignment or test
  • failure of the course
  • 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
180905
Typo corrected on Course Schedule (Test 4 date was shown as December 29)
180905
Personnel updated
180908
Notes from 180906 posted
180916
Notes from 180910, 180911, 180913 posted
180918
- Notes from 180916 posted
- Practice Test 1 posted
180918
- Solution for Practice Test 1 posted
180919
Notes from 180918 posted


























































































Return to top




Queen's University is situated on traditional Anishinaabe and Haudenosaunee Territory.