CS 2 Computational Thinking for Scientists

CS 2 Computational Thinking for Scientists

Winter 2015 - Enroll Cd: 55046 - Credits: 4
Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/cs2

Course Information

  • Course Poster:

  • Instructor: Professor Çetin Kaya Koç         → Koç is pronounced as "Coach"  

  • Class Schedule: Mon & Wed 9:30-10:45am, Phelps 3515
  • Instructor's Office Hours: Mon & Wed 1:30-3:00, Office: Phelps 1314

  • Lab/Discussion Schedules and Rooms:
    Thursday 9:00-9:50am, Phelps 3525, Enroll Cd: 55053
    Thursday 10:00-10:50am, Phelps 3525 , Enroll Cd: 55061

  • Teaching Assistant: Zhijing Li (zhijing@cs.ucsb.edu)
  • Teaching Assistant Office Hours: Tue & Fri 1:00-3:00pm
  • TA Office: Trailer 936 Room 104

  • Please join the Piazza page for class discussions  
  • Check the class website, the Piazza page, and/or your email once a day

  • Slides and course notes are in the folder docx
  • Homework and Lab documents are in the folder hwlab

  • The grades: Winter15   (The Code is your PERM number mod 9973)  

Announcements and Weekly Course Material

  • 8 Homework Assignments (due 5pm on Wednesdays)
  • 8 Lab Assignments (due 5pm on Fridays)
  • Homework Assignments and Lab Reports:
    Either, email an electronic copy to the Instructor (koc@cs) or the TA (zhijing@cs)
    Or, deliver a paper copy to the HW Box in HFH 2108
  • Electronic copy of your homework or lab report can be in Text, PDF or MS Word, or Open Office format. You could also scan/pdf your handwritten work, however, do not send phone-camera images under any circumstances!

  • Midterm Exam: Wednesday, February 11, during class
  • Final Exam: Wednesday, March 18, 8:00-11:00am, Room: Phelps 3515

  • You need COE accounts in order to use the computers in the Lab
    Open your browser and click on this link: https://accounts.engr.ucsb.edu/create
    Enter your UCSBNetId and Password, then follow the steps to set your account

  • Homework Assignment 01: hw01.pdf - due 5pm, Wed Jan 14
  • Homework Assignment 02: hw02.pdf - due 5pm, Wed Jan 21
  • Homework Assignment 03: hw03.pdf - due 5pm, Wed Jan 28
  • Homework Assignment 04: hw04.pdf - due 5pm, Wed Feb 4
  • Homework Assignment 05: hw05.pdf - due 5pm, Wed Feb 11
  • Homework Assignment 06: hw06.pdf - due 5pm, Wed Mar 4
  • Homework Assignment 07: hw07.pdf - due 5pm, Fri Mar 13

  • Lab Assignment 01: lab01.pdf - Lab on Thu Jan 8 and 15, Report due 5pm, Fri Jan 16
  • Lab Assignment 02: lab02.pdf - Lab on Thu Jan 15, Report due 5pm, Fri Jan 16
  • Lab Assignment 03: lab03.html - Lab on Thu Jan 22 and 29, Report due 5pm, Fri Jan 30
  • Lab Assignment 04: lab04.html - Lab on Thu Feb 5, Report due 5pm, Fri Feb 6
  • Lab Assignment 05: lab05.html - Lab on Thu Feb 12, Report due 5pm, Fri Feb 13
  • Lab Assignment 06: lab06.html - Lab on Thu Feb 26, Report due 5pm, Fri Feb 27
  • Lab Assignment 06: lab07.html - Lab on Thu Mar 5, Report due 5pm, Fri Mar 6

Catalog Specification

Introduction to the central concepts of computer science as they apply to a wide variety of human endeavors, including natural and physical sciences. Topics that interrelate central ideas from algorithms, performance and complexity, data structures, concurrency, languages and abstractions will be studied.

Weekly Course Plan

  • Lecture 1: Data Representation and an Overview of Computing
    What is information? How do we represent data? History of numbers and calculation, Leibniz’s system of 0’s and 1’s, analog versus digital data.
  • Lecture 2: Representation of Text
    Representation of numbers, binary, decimal, and hexadecimal number systems, representation of simple text and structured text; text encoding: 7-bit and 8-bit ASCII, Unicode, UTF-8, etc.
  • Lecture 3: Representation of Images and Video
    Representing images, intensity, pixels, tradeoffs in representation, data formats, headers, compression algorithms, optimization, Huffman coding.
  • Lecture 4: Representation of Sound and Music
    Representation of data other than text, analog sound, digital sound, sampling, digitized music, distortion, sound compression and decompression.
  • Lecture 5: Storing and Accessing Data
    Databases, Relational Databases, tables, Database Operations, join, meet, SQL, mySQL
  • Lecture 6: Iteration
    Iterative computations of sums, products, and sums of products, or products of sums. Computation of constants such pi or e.
  • Lecture 7: Recursion
    Types of recursion, recursive algorithmic paradigms, numerical examples, complexity estimates.
  • Lecture 8: Universal Computation I
    What is universality? The Turing machine model, Church-Turing thesis, time/space, determinism/nondeterminism.
  • Lecture 9: Universal Computation II
    When is a problem more difficult than another, simulations, hierarchies of problems, limits of computation, decidability, completeness.
  • Lecture 10: Arithmetic Algorithms
    Addition of integers; carry-propagate, carry-save, and carry-lookahead adders; multiplication, multiplication by shift and add, simple recursive algorithms, Karatsuba algorithm.
  • Lecture 11: Advanced Algorithms
    Linear programming, dynamic programming, and Fast Fourier Transformation.
  • Lecture 12: Searching and Sorting
    Ordering data, data structures, linear search, binary search, heap, binary tree; Sorting by searching for minimum, Bubble Sort, Quicksort, Mergesort, selection.
  • Lecture 13: Analytical versus Numerical Computation
    Solving differential equations using analytical methods, making sense of the solutions; solving differential equations using numerical methods: Euler, Runge-Kutta, pitfalls of numerical computation: Hilbert matrix, Wilkinson polynomial.
  • Lecture 14: Numerical and Symbolic Computation and Tools
    Matlab, R, and Mathematica.
  • Lecture 15: Parallelism
    Circuit-level parallelism, parallel computers, topology of connections, sharing data among processors.
  • Lecture 16: What is the Internet?
    What are protocols? HTTP, TCP/IP, routing, servers, clients, online services, big data,cloud computing.
  • Lecture 17: Everyday Cryptography
    Confidentiality and authentication, how to keep your data away from prying eyes, securing private information using encryption, how to determine with whom we are talking on the Internet, proving identity, digital signatures.

Weekly Lab Plan

  • Lab 1: Introduction
    The purpose of the lab is to obtain your COE account and to locate and experiment with some applications that we will need in the subsequent labs. The computer lab is located in Phelps 3525. We will help you to create your account and experiment with Linux, Python, and Mathematica.
  • Lab 2: Text Representation
    Students get CSIL accounts or use their own laptops; Illustrate how a simple text is a collection of bits; similar illustrations of text in other languages (Latin, Arabic, Chinese, and Japanese); Illustrate structured text (such as MS Word documents) representation.
  • Lab 3: Computing with Images
    Illustrate how a simple image is represented using cImage (Python); RGB; simple image processing, grayscaling, resizing, edge detection, image compression, and watermarking.
  • Lab 4: Interactive SQL
    Students get CSIL accounts or use their own laptops; install mySQL; learn interactive SQL commands: create a table, table structure, data and key dichotomy, add an entry, search for an entry using key, delete an entry, merge tables, split tables, other operations.
  • Lab 5: Turing Machine Programming
    How a Turing machine works and how it is programmed. Illustrate using a simulator.
  • Lab 6: Recursive Computing and Fractals
    Install and use Python and turtle module to illustrate recursive algorithms and programs. Koch curves and Hilbert Curves.
  • Lab 7: Sorting: Simple to Complicated
    Illustrate sorting algorithms using visual tools; steps of sorting algorithms (Bubble Sort, Heapsort, Quicksort and Mergesort).
  • Lab 8: Scientific Computing Tools
    Illustrate Matlab and Mathematica. Infinite precision computation. Solving equations. Plotting. Algebraic operations, symbolic computation, factoring, simplification.
  • Lab 9: Simple Networking
    IP and TCP. IP packets. Private tunnels. Secure sockets layer (SSL).

Grading Rules

  • Homework Assignments: 25 %
  • Lab Participation and Reports: 25 %
  • Midterm Exam: 25 %
  • Final Exam: 25 %

Prerequisites

  • No Level Limits
  • Letter Grade Only
  • Major Limits: Engineering students cannot enroll
  • Prerequisites: Math 4a with a grade of C or better

Academic Integrity at UCSB  


Dr. Çetin Kaya Koç