Introduction to Computer Science (Fall 2017)


Course:

Introduction to Computer Science (CH08320101)

Instructor:

Jürgen Schönwälder

TA:

Steven Abreu,
Malte Aaron Granderath,
Alexandru Hambasan,
Tudor Cristian Maiereanu,
Mohit Shrestha,
Mihail Tarigradschi

Lectures:

Tuesday 
08:15  09:30 
Lecture Hall Research II 
Tuesday (Tutorials) 
09:45  11:00 
Lecture Hall Research II 
Thursday 
11:15  12:30 
Lecture Hall Research II 

Start:

September 5, 2017

Contents:

The course covers the fundamental concepts and techniques
of computer science in a bottomup manner. Based on clear
mathematical foundations (which are developed as needed)
the course discusses abstract and concrete notions of
computing machines, information, and algorithms, focusing
on the question of representation versus meaning in
Computer Science.
To develop a theoretical notion of computation, we
introduce basic concepts of discrete mathematics with a
focus on inductively defined structures. The functional
programming language Haskell will be introduced and used
as the primary programming language for the course. We
cover a basic subset of Haskell that includes types,
recursion, tuples, lists, strings, and higherorder
functions. Back on the theoretical side, we cover the
syntax and semantics of Boolean expressions and we explain
how Boolean algebra relates to logic gates and digital
circuits. On the technical side, we introduce the
representation of basic data types such as numbers,
characters, strings and dates as well as the basics of
computer architecture and assembly programming. On the
algorithmic side, the course introduces the notion of
correctness and elementary complexity theory (bigO
notation) and we introduce abstract data types.

Course Materials:


Books:


Links:


Schedule: 
Tue (08:15)  Thu (11:15)  Topics 
20170905 
20170907 
Introduction and maze generation algorithms 
20170912 
20170914 
String search algorithms, complexity and correctness 
20170919 
20170921 
Mathematical notations and proof techniques 
20170926 
20170928 
Sets, relations, and functions 
20171003 
20171005 
Representation of integer and floating point numbers 
20171010 
20171012 
Representation of characters, strings, date and time 
20171017 
20171019 
Boolean operations and expressions 
20171024 
20171026 
Boolean algebra and normal forms 
20171031 
20171102 
Boolean expression minimization and Boolean logic 
20171107 
20171109 
Logic gates, basic digital circuits, von Neuman computer architecture 
20171114 
20171116 
Assembly programming, interpreter, compiler 
20171121 
20171123 
Operating systems, processes, file systems, communication 
20171128 
20171130 
Finite state machines, pushdown automata and turing machines, formal languages 
20171205 
20171207 
Computability theory and complexity theory 

Tutorials: 
Tue (09:45)  Topics 
20170905 

20170912 
Haskell Tutorial (Alexandru) 
20170919 
Shell Tutorial (Steven) 
20170926 
Haskell Tutorial (Alexandru) 
20171003 

20171010 
Lecture (moved from 20171005) 
20171017 
Haskell Tutorial (Alexandru) 
20171024 
Grand Tutorial 
20171031 

20171107 

20171114 
Haskell Tutorial (Alexandru) 
20171121 
Haskell Tutorial (Alexandru) 
20171128 

20171205 
Grand Tutorial 
Tue (11:00)  Topics  Location 
20171212 
Grand Tutorial (Practice Sheet) 
CS Lecture Hall, Research I 

Groups: 
Day  Time  Room  TA 
Fri  20:0021:00  Mercator College  Mihail Tarigradschi 
Sat  20:0021:00  Krupp College  Mohit Shrestha 
Sun  14:3015:30  Nordmetall Conference Room  Alexandru Hambasan 
Sun  16:0017:00  Mercator Conference Room  Tudor Cristian Maiereanu 
Sun  20:0021:00  College 3 QSA  Malte Aaron Granderath 
Mon  20:0021:00  College 3 QSA  Steven Abreu 

Dates:

Date/Due  Name  Topics 
20170912  Quiz #1  administrivia, mazes, kruskal's algorithm 
20170919  Quiz #2  complexity, correctness, software engineering, mathematical notation 
20170919  Problem Sheet #1  boyer moore bad character rule, haskell factorial 
20170926  Quiz #3  proof techniques 
20170926  Problem Sheet #2  proof by contrapositive and by induction 
20171003  Problem Sheet #3  sets and relations 
20171010  Quiz #4  relations, functions, recursion 
20171010  Problem Sheet #4  order relations, function composition 
20171017  Quiz #5  units, prefixes, characters, date and time 
20171017  Problem Sheet #5  number systems, floating point numbers 
20171024  Quiz #6  boolean algebra and logic 
20171026  Midterm Exam  (Eastwing) 
20171031  Problem Sheet #6  boolean expressions, tower of hanoi 
20171107  Quiz #7  normal forms, complexity of boolean functions, quinemccluskey 
20171107  Problem Sheet #7  quinemccluskey algorithm 
20171114  Quiz #8  von Neumann computer architecture 
20171114  Problem Sheet #8  half and full adder, ripple carry adder and carry lookahead adder 
20171121  Quiz #9  assembly programming, interpreter, compiler 
20171121  Problem Sheet #9  assembly programming 
20171128  Quiz #10  operating systems 
20171128  Problem Sheet #10  fold functions, processes 
20171205  Quiz #11  automata (bonus) 
20171205  Problem Sheet #11  automata and formal languages (bonus) 
20171216  Final Exam  09:0011:00 East Wing (closed book) 
20180210  Makeup Final Exam  14:0016:00 CS Lecture Hall (closed book) 

Results:


Grading:

The final grade is made up of the final exam (30 %),
quizzes (30 %), the midterm exam (20%) and homework
assignments (20 %). It is required to submit the solution
for homeworks assignments electronically. Late submissions
will not be accepted. Homeworks may need to be defended in
an oral interview.
Any programs which have to be written will be
evaluated based on the following criteria:
 correctness including proper handling of error conditions
 proper use of programming language constructs
 clarity of the program organization and design
 readability of the source code and any output produced
Source code must be accompanied with a README providing an
overview of the source files and giving instructions how
to build the programs. A suitable Makefile is required if
the build process involves more than a single source file.
For any questions stated on assignment sheets, quiz
sheets, exam sheets or during makeups, we by default
expect a reasoning for the answer given, unless
explicitely stated otherwise.
