# [CMPSC 24] - Midterm Exam Guide - Everything you need to know! (41 pages long)

For unlimited access to Study Guides, a Grade+ subscription is required.

UCSB

CMPSC 24

MIDTERM EXAM

STUDY GUIDE

The essence of the computational procedure

○

Step by step instructions

○

Algorithms

•

Implementation of the algorithm

○

Programs

•

The organization of data/information needed to solve the problem

○

Data structures / abstract data types

•

Problem Solving with Computers

Specification of input --> ALGORITHM --> specification of output in terms of input

•

Solution space: number of possible ways (algorithms) to solve the problem

•

Algorithmic Problem/Solution

Running time of an algorithm with respect to the size of the input

Implement all the algorithms (--> programs)

□

Data selection of varying size/distribution

□

Identical set-up (hardware/software)

□

Measure the running time experimentally (time vs input size/distribution)

Time

○

Space

○

Efficient

•

What is a Good Algorithm?

Mix of natural language and high-level programming concepts

Pseudocode

○

High-level description instead of programing implementation

•

Size + distribution

○

Account for all possible inputs

•

Insensitive to the underlying hardware/software architecture

•

Methodology to Reason About Algorithm Efficiency

More structures than usual prose

•

Less formal than a programming language

•

<-- for assignment (=)

○

=, ≠for boolean equals (==, !=)

○

Numerical and boolean expressions

•

If… then… else…

•

For… do

Repeat.…until

While.…do

•

Name (args)

○

Return value

○

Function

•

Pseudocode

Correctness

•

Number of elements

Distribution of input

Algorithm

Depends on

○

Efficiency (running time)

•

Algorithm Design

Lecture 1

Lecture 1

Tuesday, January 10, 2017

9:44 AM

CMPSC 24 Page 1

find more resources at oneclass.com

find more resources at oneclass.com

Lecture 1

CMPSC 24 Page 2

find more resources at oneclass.com

find more resources at oneclass.com