Foundation Exam Review: Tips, Structure & Strategies
Foundation Exam Review
Session
Exam Structure and Tips
Arup Guha May 10, 2018
Exam Sections
•
Data Structures
•
Dynamic Memory Management
•
Linked Lists
•
Stacks/Queues
•
Binary Trees
•
Hash Tables/Heaps
•
AVL Trees/Tries
•
Algorithms and Analysis Tools
•
Algorithm Analysis
•
Timing Questions
•
Summations/Recurrence Relations
•
Recursive Coding
•
Sorting
•
Brute Force Tools (Bitwise ops,
backtracking)
Exam Parameters
•
Twelve Questions broken into four separate sections of three
questions each.
•
120 minutes total (so roughly 10 minutes per question)
•
Get the whole exam at the beginning
•
Have freedom to spend more or less time on each question.
•
No Calculator
•
Only Aid is posted Formula Sheet (has descriptions of functions from
common C libraries that may need to be called in some solutions to
problems and some summation formulas)
Exam Eligibility Rules
•
Must pass COP 3502 with a C or higher (or equivalent if transferring).
•
Must be Computer Science major to take the exam.
•
Must be within one year of passing COP 3502 to take the exam. (This
limits the number of attempts to at most three.)
•
Exception – students who change to majoring in Computer Science
after taking COP 3502 or transfer to UCF after taking the equivalent
course. In these cases, students are eligible to take the exam for 12
months from the time they change to majoring in Computer Science
or transferring to UCF.
Relevant Exam Statistics
•
Detailed stats can be found here, sorted by exam:
http://www.cs.ucf.edu/registration/exm/
•
Since 2001, of 6532 exam attempts, 2962 were passed, for a historical
passing rate of 45%.
•
Under the new exam format, 602 students have passed out of 1245
exam attempts, for a passing rate of 48.35%
•
I don’t have recent data for this, but from 2001-2010, 75% of the
students who attempted the exam at least once, eventually passed it.
Key Strategies for Success
•
Routinely sleep and exercise well.
•
Start studying several weeks before the exam. Do so regularly. Do
NOT cram.
•
Use both focused study sessions (one topic only) and diffuse ones
(practice exam).
•
Study in different places/times.
•
Focus on testing (practice questions) instead of reading over notes.
•
Write code (linked lists, binary trees, trie) from scratch!!!
•
Read the whole exam within the first 15 or 20 minutes of the exam so
you can properly plan what order to do the questions.
Review Session Activity
•
Get into groups of size 3-6.
•
Each group gets a question I give them at random from a past exam.
•
Discuss the concepts the question tests as well as any specific items the
question maker might be targeting.
•
Answer the question: How is the question maker trying to make sure that
the student has a conceptual understanding of the topic at hand instead of
just memorizing a solution to a past test question?
•
Write your own question that tests the concept(s) in the question you were
given, but make it appear different enough. Also try to make it so that
someone who memorized the solution to the prior question would have
trouble answering your question without a general conceptual
understanding of the item at hand.
Spring Exam 2017 – DSB Q1
•
Concept tested – selectively going through parts of a binary search
tree based on a new problem.
•
Method of Testing to Ensure understanding – In most BST problems,
either all node are visited or one path of the tree is visited. That is not
the case in this problem. Sometimes we go down both subtrees and
other times we go down one subtree. In addition, most BST code
shown in class uses integers. Strings are used in the class frequently,
so a good way to test application of string functions is to see if
students can figure out where to appropriately call string functions
(and which ones) in the context of a problem with binary trees.
Spring Exam 2017 – AAB Q3
•
Concept tested – Custom changing the general mold of a backtracking
solution to a new problem.
•
Method of Testing to Ensure understanding – problem is different
than the usual backtracking examples (8 Queens, Maze) in that the
number of potential options for the “kth slot” isn’t variable. Since we
are successively placing digits in the number that we are forming
there are always 10 options for the next slot (except the first slot for
which there are 9). In addition, divisibility is a focus of the course, but
isn’t usually used in the backtracking examples shown in class, so this
is a perfect blending of two concepts, testing if students can apply
their understanding of divisibility and digit value in the context of
solving a problem with a backtracking mold.
Summer Exam 2017 – DSA Q1
•
Concept tested – nested memory allocation structure where an array
of pointers is dynamically allocated, and then each of those pointers
will point to new dynamically allocated memory of various sizes.
•
Method of Testing to Ensure understanding – Information is given in a
slightly different way than past questions, where it must be read from
a file pointer passed into a function. Also, having each different array
in the array of arrays be of different sizes requires a structural
understanding of the two levels of pointers.
Summer Exam 2017 – AAA Q3
•
Concept tested – recurrence relation iteration technique
•
Method of Testing to Ensure understanding – Though these are fairly
straight-forward, occasionally students memorize the exact
recurrence relations shown in class. One of these is T(n) = 2T(n/2) +
O(n), the recurrence for Merge Sort. This question was intentionally
designed to look similar with one simply change, the O(n
2
), which
changes the overall answer. Also, the mathematics changes
somewhat significantly. So understanding is ensured as students are
required to notice this difference and then faithfully work out the
math (which turns out to be different) with that once change.
Fall Exam 2017 – DSB Q3
•
Concept tested – extracting novel information from a trie structure.
•
Method of Testing to Ensure understanding – in the code shown in class, either a
word is inserted or searched for in a trie, and perhaps some basic statistic is
calculated. Here, you are asked to find the number of unique words that contain
a particular letter, more than likely, a new task. What also makes this task more
difficult is that it requires fully understanding what is being asked and the use of
an extra piece of information in a trie node (numwords) that isn’t stored in a basic
trie node struct. The point of the exercise (when I edited this question I had a
very clear goal in mind) was to prove to the student that some tasks can become
much easier on a trie if you store extra information in each node. This is a classic
time-memory trade off. While I realized that most students wouldn’t get to this
realization during the exam, I wanted to try to create that “aha” moment for a
few students, as these were some of my favorite moments when taking exams in
college. (I loved learning something while I was taking an exam.)
Fall Exam 2017 – AAA Q3
•
Concept tested – recognizing processes similar to Insertion Sort and Merge
Sort without the words being used, and then being able to carry out the
analysis of the adjusted algorithm.
•
Method of Testing to Ensure understanding – In the regular sorts, the size
of the input is n values. In this question, the size of the input is n lists of size
n, so a total of n
2
values. This difference adjusts the set up of the
mathematical analysis, but ultimately, after the equations are set up, n can
be pulled out as a constant in the respective summations leaving
mathematics that is identical to what is necessary to analyzed the two
aforementioned sorts. Not using the words “insertion sort” and “merge
sort” as well as adjusting the problem with a different sized input are the
mechanisms used in this question to ensure that whoever answers it
correctly truly understands the underlying concepts.
Spring Exam 2018 – DSA Q3
•
Concept tested – understanding the steps of the algorithm to
evaluate a postfix expression as well as how to use stack functions,
when given these in a library.
•
Method of Testing to Ensure understanding – Typically, on past exams,
this question was asked as a tracing question, with a specific postfix
expression to evaluate. If a student can do that reliably, then they
know the general steps to solve the problem. Thus, this question is
making sure a student can convert those general steps into code, as
well as use the stack functions given as they are documented. This
conversion (unlikely to have been done by a student in the past)
ensures understanding of the algorithm.
Spring Exam 2018 – AAB Q1
•
Concept tested – recognizing that the algorithm described is actually
one taught in the course: binary search. Secondarily, coding that
algorithm is also tested.
•
Method of Testing to Ensure understanding – If the question read,
“Write a recursive binary search”, students who had just memorized
the recursive binary search from class would get full credit. In
intentionally describing the algorithm without using its name, the
question ensures that students know what a binary search is, and can
identify a description of it. Thus – either a question might ask for a
new algorithm, or if it asks for one definitively covered in the course,
it might not use it’s name to ensure conceptual understanding of the
student.
Delve into the Foundation Exam review session insights by Arup Guha covering exam sections, parameters, eligibility rules, and key success strategies for aspirants. Gain valuable exam statistics and engage in group review activities to enhance understanding and preparation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Foundation Exam Review Session Exam Structure and Tips Arup Guha May 10, 2018
Exam Sections Data Structures Dynamic Memory Management Linked Lists Stacks/Queues Binary Trees Hash Tables/Heaps AVL Trees/Tries Algorithms and Analysis Tools Algorithm Analysis Timing Questions Summations/Recurrence Relations Recursive Coding Sorting Brute Force Tools (Bitwise ops, backtracking)
Exam Parameters Twelve Questions broken into four separate sections of three questions each. 120 minutes total (so roughly 10 minutes per question) Get the whole exam at the beginning Have freedom to spend more or less time on each question. No Calculator Only Aid is posted Formula Sheet (has descriptions of functions from common C libraries that may need to be called in some solutions to problems and some summation formulas)
Exam Eligibility Rules Must pass COP 3502 with a C or higher (or equivalent if transferring). Must be Computer Science major to take the exam. Must be within one year of passing COP 3502 to take the exam. (This limits the number of attempts to at most three.) Exception students who change to majoring in Computer Science after taking COP 3502 or transfer to UCF after taking the equivalent course. In these cases, students are eligible to take the exam for 12 months from the time they change to majoring in Computer Science or transferring to UCF.
Relevant Exam Statistics Detailed stats can be found here, sorted by exam: http://www.cs.ucf.edu/registration/exm/ Since 2001, of 6532 exam attempts, 2962 were passed, for a historical passing rate of 45%. Under the new exam format, 602 students have passed out of 1245 exam attempts, for a passing rate of 48.35% I don t have recent data for this, but from 2001-2010, 75% of the students who attempted the exam at least once, eventually passed it.
Key Strategies for Success Routinely sleep and exercise well. Start studying several weeks before the exam. Do so regularly. Do NOT cram. Use both focused study sessions (one topic only) and diffuse ones (practice exam). Study in different places/times. Focus on testing (practice questions) instead of reading over notes. Write code (linked lists, binary trees, trie) from scratch!!! Read the whole exam within the first 15 or 20 minutes of the exam so you can properly plan what order to do the questions.
Review Session Activity Get into groups of size 3-6. Each group gets a question I give them at random from a past exam. Discuss the concepts the question tests as well as any specific items the question maker might be targeting. Answer the question: How is the question maker trying to make sure that the student has a conceptual understanding of the topic at hand instead of just memorizing a solution to a past test question? Write your own question that tests the concept(s) in the question you were given, but make it appear different enough. Also try to make it so that someone who memorized the solution to the prior question would have trouble answering your question without a general conceptual understanding of the item at hand.
Spring Exam 2017 DSB Q1 Concept tested selectively going through parts of a binary search tree based on a new problem. Method of Testing to Ensure understanding In most BST problems, either all node are visited or one path of the tree is visited. That is not the case in this problem. Sometimes we go down both subtrees and other times we go down one subtree. In addition, most BST code shown in class uses integers. Strings are used in the class frequently, so a good way to test application of string functions is to see if students can figure out where to appropriately call string functions (and which ones) in the context of a problem with binary trees.
Spring Exam 2017 AAB Q3 Concept tested Custom changing the general mold of a backtracking solution to a new problem. Method of Testing to Ensure understanding problem is different than the usual backtracking examples (8 Queens, Maze) in that the number of potential options for the kth slot isn t variable. Since we are successively placing digits in the number that we are forming there are always 10 options for the next slot (except the first slot for which there are 9). In addition, divisibility is a focus of the course, but isn t usually used in the backtracking examples shown in class, so this is a perfect blending of two concepts, testing if students can apply their understanding of divisibility and digit value in the context of solving a problem with a backtracking mold.
Summer Exam 2017 DSA Q1 Concept tested nested memory allocation structure where an array of pointers is dynamically allocated, and then each of those pointers will point to new dynamically allocated memory of various sizes. Method of Testing to Ensure understanding Information is given in a slightly different way than past questions, where it must be read from a file pointer passed into a function. Also, having each different array in the array of arrays be of different sizes requires a structural understanding of the two levels of pointers.
Summer Exam 2017 AAA Q3 Concept tested recurrence relation iteration technique Method of Testing to Ensure understanding Though these are fairly straight-forward, occasionally students memorize the exact recurrence relations shown in class. One of these is T(n) = 2T(n/2) + O(n), the recurrence for Merge Sort. This question was intentionally designed to look similar with one simply change, the O(n2), which changes the overall answer. Also, the mathematics changes somewhat significantly. So understanding is ensured as students are required to notice this difference and then faithfully work out the math (which turns out to be different) with that once change.
Fall Exam 2017 DSB Q3 Concept tested extracting novel information from a trie structure. Method of Testing to Ensure understanding in the code shown in class, either a word is inserted or searched for in a trie, and perhaps some basic statistic is calculated. Here, you are asked to find the number of unique words that contain a particular letter, more than likely, a new task. What also makes this task more difficult is that it requires fully understanding what is being asked and the use of an extra piece of information in a trie node (numwords) that isn t stored in a basic trie node struct. The point of the exercise (when I edited this question I had a very clear goal in mind) was to prove to the student that some tasks can become much easier on a trie if you store extra information in each node. This is a classic time-memory trade off. While I realized that most students wouldn t get to this realization during the exam, I wanted to try to create that aha moment for a few students, as these were some of my favorite moments when taking exams in college. (I loved learning something while I was taking an exam.)
Fall Exam 2017 AAA Q3 Concept tested recognizing processes similar to Insertion Sort and Merge Sort without the words being used, and then being able to carry out the analysis of the adjusted algorithm. Method of Testing to Ensure understanding In the regular sorts, the size of the input is n values. In this question, the size of the input is n lists of size n, so a total of n2values. This difference adjusts the set up of the mathematical analysis, but ultimately, after the equations are set up, n can be pulled out as a constant in the respective summations leaving mathematics that is identical to what is necessary to analyzed the two aforementioned sorts. Not using the words insertion sort and merge sort as well as adjusting the problem with a different sized input are the mechanisms used in this question to ensure that whoever answers it correctly truly understands the underlying concepts.
Spring Exam 2018 DSA Q3 Concept tested understanding the steps of the algorithm to evaluate a postfix expression as well as how to use stack functions, when given these in a library. Method of Testing to Ensure understanding Typically, on past exams, this question was asked as a tracing question, with a specific postfix expression to evaluate. If a student can do that reliably, then they know the general steps to solve the problem. Thus, this question is making sure a student can convert those general steps into code, as well as use the stack functions given as they are documented. This conversion (unlikely to have been done by a student in the past) ensures understanding of the algorithm.
Spring Exam 2018 AAB Q1 Concept tested recognizing that the algorithm described is actually one taught in the course: binary search. Secondarily, coding that algorithm is also tested. Method of Testing to Ensure understanding If the question read, Write a recursive binary search , students who had just memorized the recursive binary search from class would get full credit. In intentionally describing the algorithm without using its name, the question ensures that students know what a binary search is, and can identify a description of it. Thus either a question might ask for a new algorithm, or if it asks for one definitively covered in the course, it might not use it s name to ensure conceptual understanding of the student.
