FREE lectures this July. Places booking out fast. HSC: book here. VCE: book here.

Welcome, Guest. Please login or register.

June 25, 2019, 09:31:36 pm

Author Topic: Algorithmics Thoughts  (Read 810 times)

0 Members and 1 Guest are viewing this topic.

stevenhuyn

  • Trailblazer
  • *
  • Posts: 32
  • Respect: +17
Algorithmics Thoughts
« on: January 03, 2018, 10:14:22 pm »
+14
VCE Algorithmics 3/4 Thoughts
Hello, I finished VCE Algorithmics in 2017 and will be writing about some thoughts. I was in a position last year trying to find information about Algorithmics and there was nearly nothing. So just wanted to put something up.

About This Subject
The best I could describe this subject as it a technical Software Development in terms of the SACs, exams and question styles. I don’t think you absolutely need a strong background in mathematics, as long as you have the learning aptitude to learn mathematical content and a healthy appreciation for it is enough.

This subject is a keyword subject, where you apply the skills into the situations and prompts in the exams. So one can do pretty well at this subject on the SACs and the exam without having programmed a single line of code by just understanding the content well enough. (Still need to write pseudocode though)

Since not many teachers would be good at teaching this and rightfully it is a new and difficult subject, self learning and evaluation is important. Consistently check your understanding of the topics. You should know by now that it is up to you to learn the content in VCE yourself.

Official Online Textbook Contents
https://www.alexandriarepository.org/syllabus/vce-algorithmics-2017-edition
Spoiler
•   1 Algorithmics – The heart of computer science
o   1.1 Why Study Algorithmics
o   1.2 What is an Algorithm?
o   1.3 The Muddy City Problem
o   1.4 Algorithmics versus Coding
o   1.5 Data: from messy to beautiful
•   2 Algorithmic Problem Solving
o   2.1 Graphs and Networks
   2.1.1 Modelling with Graphs
   2.1.2 Modelling States of the World
   2.1.3 Decision Trees
   2.1.3.1 Sorting with Decision Trees
   2.1.4 Formal Definition of Graphs
o   2.2 Graph Algorithms: Revisiting the Muddy City
o   2.3 Searching in networks: a first look
o   2.4 How to write an algorithm
   2.4.1 Sequences
   2.4.2 Variables and Assignments
   2.4.3 Decisions
   2.4.4 Repetition and Iteration
   2.4.5 Blocks
   2.4.6 Nesting
   2.4.7 Abstraction and Modularization
   2.4.7.1 Parameters
   2.4.7.2 Return Values
   2.4.8 Collections
   2.4.9 Converting Pseudocode into Edgy
o   2.5 Edgy: Revisiting the Muddy City
o   2.6 Breadth First Search and Depth First Search (2016)
   2.6.1 Browsing a social network using BFS
o   2.7 Abstract Data Types
   2.7.1 Why ADTs Matter
   2.7.2 The Graph ADT
   2.7.3 Collection ADTs: Lists and Arrays
   2.7.4 More Collection ADTs
   2.7.5 Application: Graph Traversal
   2.7.6 An extreme example: integers
o   2.8 Networks of Actions: Planning and Decision Making
   2.8.1 Suspicious Boyfriends
   2.8.2 Building the graph
   2.8.3 Planning: putting it all together
o   2.9 Path Finding
   2.9.1 Dijkstra’s Shortest Path Algorithm
   2.9.2 Bellman-Ford’s Shortest Path Algorithm
   2.9.3 Warshall’s Transitive Closure Algorithm
   2.9.4 Floyd’s Algorithm for All-Pair Shortest Paths
o   2.10 PageRank
o   2.11 Algorithmic Complexity: How fast is my algorithm?
o   2.12 Recursion
   2.12.1 What is recursion? A brief introduction
   2.12.2 What is recursion: simple examples
   2.12.3 Decrease and Conquer
   2.12.4 How to draw a tree
   2.12.5 Recursive tree search (video)
   2.12.6 Recursive Graph Traversal by DFS
   2.12.7 Analysing recursive algorithms
o   2.13 Best First Search
o   2.14 Applied Algorithms (DRAFT)
•   3 Principles of Algorithm Design
o   3.1 Big-O notation: a brief introduction
o   3.2 Algorithm analysis: a primer
o   3.3 Divide and Conquer
   3.3.1 Binary Search Trees
o   3.4 Complexity of Recursive Algorithms
   3.4.1 Solving a Recurrence Relation by Telescoping
   3.4.2 The Master Theorem for Divide and Conquer
   3.4.3 Recursive Complexity: An Example
o   3.5 Dynamic Programming
o   3.6 Game Trees and the Minimax Algorithm
o   3.7 Computationally Hard Problems
   3.7.1 Travelling Salesman Problem
   3.7.2 NP-Hard Problems: Soft Limits of Computation
   3.7.3 Heuristics
   3.7.4 Heuristics for the Graph Colouring Problem
•   4 Turing Machines and the Origin of Computer Science
o   4.1 Hilbert’s Program
o   4.2 Alan Turing and the Turing Machine
o   4.3 Busy Beavers
o   4.4 Undecidability and The Halting Problem: Hard Limits of Computation
o   4.5 A Weird Computational Formalism
o   4.6 A short Introduction to the General History of Computing
•   5 Searle’s Chinese Room Argument
•   6 DNA Computing a la Adleman
•   7 Appendix A: Extension materials
o   7.1 Being Harry Houdini
o   7.2 Semantic Specification of Abstract Data Types
o   7.3 Tail Recursion
   7.3.1 Exercises: recursive list idioms in Edgy
   7.3.1.1 Solutions: recursive list idioms in Edgy
   7.3.1.2 Solutions: Append and Reverse in Edgy
o   7.4 Testing Algorithm Correctness
•   8 Appendix B: The VCE study “Algorithmics”
o   8.1 VCE “Algorithmics”
o   8.2 Textbooks for VCE “Algorithmics”
o   8.3 Learning for Algorithmics and Computer Science
o   8.4 Recommeded Progression
   8.4.1 Recommended Progression – Unit 3
   8.4.2 Recommended Progression – Unit 4
•   9 Test Your Knowledge
o   9.1 Review Unit 3, Outcome 1
o   9.2 Review Unit 3, Outcome 2

SAT
A 3 part SAT based a prompt that was the same for every student where we had to devise and design a data structure to encapsulate a friendship and movie network. This was to be completed with either language Edgy or Python to visualise your network. I was one of 3 or 4 in my class to usePython and the networkx module instead of Edgy. The first part we describe the data model and how information will be represented. The second part are the algorithms where we write pseudocode and explain it. The final part is testing and evaluating the code, whether it was effective and its limits.

SACs
Tests on algorithm design, dynamic programming, graph algorithms and data structures. There was always a small question at the end to tease out those looking for a brain teaser that took up a lot of the time, because there isn’t a lot of hard questions that can be asked about these.

Oral (Outcome 3)
A oral with a submitted writeup on the history of computation. Wikipedia articles are more than enough. Be prepared to spend time actually knowing this stuff inside and out. The extra parts we were told to look at as said from VCAA bulletin was neural networks and DNA computing which were pretty interesting to look at.

Exam
The exam looked very intimidating but was fair, it felt like a Software Development exam honestly, except it was 20% multiple choice and 80% long answer case studies (10 marker type things). I remember during reading time I was shaking my head because they were seemingly hard and a few questions took a few too many re reads to fully understand simply the prompt. It did not help that no one in my class finished reading the paper during the time allocated for reading, however I finished the exam in the end happily.

My Thoughts/Context
The subject was a very good pickup for me, I am so very glad my school offered it, as it formally cemented all the knowledge I was blindly absorbing from Wikipedia articles, computerphile and from comp sci minded peers, spurred on from jumping into the land of Python the previous year in anticipation for Software Development 3/4.

I really recommend this route. Learn Python, do Software Development and then Algorithmics. Softdev gives you a broad perspective whereas Algorithmics will go into the technical part of comp sci.

What I disliked about the subject was that as the online textbook is constantly being revised at the start of each year. It was vague at times and was difficult to dissect information and definitions in a few chapters. I also found that with some of the later chapters relying solely on a video, with no accompanying text, it made it annoying to revise the topic as you had to watch the whole video again.

How to Prepare
Before the end of 2016, our teacher told us to have a read over the complete textbook, giving us the login for the textbook, completing a small amount of chapters as holiday homework, while also getting our hands dirty in Edgy.  I read through about half the textbook before it stopped halfway because it started getting too much for me to hold in.

Bare minimum, skim the first few chapters of the textbook, and do some exercises in Edgy. If you are a keen bean, learn Python as well! It's not hard and will let you test a lot of the content yourself in your own time.

Do this subject if you
Interested in Computer Science.
Enjoy puzzles and problems.
Enjoy learning a tool, its limits and how to apply it.

Don’t if you...
Hate or fear math notation or math in general.
Not prepared to spend time on difficult concepts.

Everything Else
Spoiler
Crosslinks with other Subjects

Software Development 3/4
• The SAT was insane practice for writeups. Learning about scope and the SAT was good practice for this one.
• Quicksort and selection sort will probably turn up in algorithmics as part of learning time complexity and problem solving strategies. Respectively divide and conquer and decrease and conquer.
• Data types and structures. If you remember vaguely the data structures you can get their benefits and weaknesses, the reasoning skills of this is used when answering compare type questions in Algorithmics,
• Software design concepts.
• Pseudocode practice!
• Learning a programming language!!

Specialist 1/2
• Proof by induction and contradiction. Was nice to already have been introduced to the concepts the year before formally, helped ease the concepts again when it was taught again.
• Matrix multiplication, useful for 1 small topic.

English 1/2
• I did a book called Logicomix which was a graphic novel based on Bertrand Russel and his paradox, the person who was the precursor to computer science theory. Was a very nice study having the context. Sadly didn’t learn anything about Godel in Algorithmics though. Conveniently it was the entire topic of outcome 3.

Further
• I didn’t do Further, but there is a module about networks and graphs where you even learn Dijkstra’s algorithm! A senior above me said that Further and Algo were not a bad combo and my teacher was drawing comparisons during the year.

What I/classmates found challenging/what to look out for
•   Dynamic Programming: Memoization, Tabulation, Bottom-up, Top-down, know the differences!
•   Telescoping and reccurance relations.
•   Grasping the history of computability and how in depth we need to know for the exam. (There was a 10 marker question to sumamrise it on the exam)
•   P vs NP
•       Using "transitive closure" in a sentence

Wholesome Blog
http://www.ramblingteacher.com/2015/10/the-epic-that-was-vce-algorithmics-2015.html
http://www.ramblingteacher.com/2014/11/vce-algorithmics-journey-begins.html

Basing my review off of
https://atarnotes.com/forum/index.php?topic=43031.msg606977;topicseen#msg606977

Feel free to ask anything! Sorry if it's a little low quality.
« Last Edit: January 05, 2018, 02:28:24 pm by stevenhuyn »

Aaron

  • Honorary Moderator
  • ATAR Notes Legend
  • *******
  • Posts: 3716
  • Respect: +1282
Re: Algorithmics Thoughts
« Reply #1 on: January 03, 2018, 10:15:35 pm »
+4
Thanks so much for taking the time to make this! I have added your thread to our Algorithmics Resources sticky.
BInfoTech (LTU), MTeach SecEd (Monash) Maths/IT

Current secondary teacher in Maths and Computing.
Experienced teaching at both secondary and university level.

My Website | Music History | Footy Tipping 2k19