COMS W1004 Lecture Notes - Lecture 1: Computer Architecture, Simon & Garfunkel, Von Neumann Architecture
7 May 2018
School
Department
Course
Professor
COMS W1004 – Introduction to Computer Science in Java
Spring 2018
Midterm Recitation
DATE: 3/2/18
FORMAT:
- How long will the midterm be?
o ~50 questions (
- What types of questions will be asked?
o Expect mostly multiple choice similar to the example questions, but there will be a
vocabulary section
o Prof. Cannon does not share the exam with TAs beforehand, we can’t say for sure how
long it will be or how questions will be asked
- What content will be covered? / How should I study
o Review all code discussed in class (e.g., BankAccount)
o Review and understand the solutions to problem sets and programming projects
o Review the material in the textbook(s): S&G 1-5, Horstmann, 1-6, 8
TOPICS:
1. Theory
a. Analysis of Algorithms (understanding Big-O notation; search algorithms, sorting
algorithms, average vs. worst case, etc.)
b. Representing Information (binary notation; hexadecimal notation; two’s complement
notation; binary addition/subtraction)
c. Boolean Logic / Circuits (AND, OR, NOT, NAND, NOR, XOR, etc.)
d. Computer Architecture (Von Nuemann)
2. Programming / Object-Oriented Design in Java
a. Primitive Data Types and Objects
i. The String API
b. Control Flow and Iterations
c. Building and Using Classes (types of classes, types of methods, “definition” vs.
“initialization” vs. “instantiation”; “implicit parameter” vs. “explicit parameter”; “actual”
vs. “formal” parameter)
Please Note: the examples in parentheses are not exhaustive sub-topics
QUESTIONS:
1) There are three kinds of errors in Java, what are they and how are they different?
2) Name all the primitive data types in Java and how many bytes they take up in memory.
3) What’s the worst-case runtime of selection sort? What about for insertion sort?
4) What is the decimal number forty-two in binary? What is it in hexadecimal notation? What about
octal notation?
5) Can you name all the components of the Von Neumann architecture of a computer? What is the
functionality of each component?
SCHDULE:
1 MIN – Introduce the exam format, and ask if anyone has any logistical questions / questions about the
exam format
5 MIN – Introduce the topics to expect on the exam; poll the class to determine topics of focus; remember
to ask if there’s anything that anyone would like to cover that’s not yet on the board
15-20 MIN – Review the sample questions that Professor Cannon released
15 MIN – Analysis of Algorithms:
- Big-O Notation
o T(N) vs. O(N)
o Examples:
What’s the Big-O of the following:
1)
for(int i = 0; i < n; i++)
{
// body
}
2)
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; i++)
{
// body
}
}
3)
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 1000; i++)
{
// body
}
}
[SAMPLE PROBLEM 1]
- Insertion Sort vs. Selection Sort:
Selection Sort
Algorithm to sort the items on a list into nondecreasing
order
Input:
A list of
N => 1 elements A[1], A[2], ... , A[n].
Output:
The list sorted in nondecreasing order.
Document Summary
Coms w1004 introduction to computer science in java. How long will the midterm be: ~50 questions ( / how should i study: review all code discussed in class (e. g. , bankaccount, review and understand the solutions to problem sets and programming projects, review the material in the textbook(s): s&g 1-5, horstmann, 1-6, 8. Initialization vs. instantiation ; implicit parameter vs. explicit parameter ; actual vs. formal parameter) Please note: the examples in parentheses are not exhaustive sub-topics. 1 min introduce the exam format, and ask if anyone has any logistical questions / questions about the exam format. 5 min introduce the topics to expect on the exam; poll the class to determine topics of focus; remember to ask if there"s anything that anyone would like to cover that"s not yet on the board. 15-20 min review the sample questions that professor cannon released. Big-o notation: t(n) vs. o(n, examples: // body for(int j = 0; j < n; i++)
