es/iode’s Post

📃Scientific paper: A Reusable Machine-Calculus for Automated Resource Analyses;Une machine abstraite réutilisable pour les analyses de ressources Abstract: International audience; An automated resource analysis technique is introduced, targeting a Call-By-Push-Value abstract machine, with memory prediction as a practical goal. The machine has a polymorphic and linear type system enhanced with a first-order logical fragment, which encodes both low-level operational semantics of resource manipulations and high-level synthesis of algorithmic complexity. Resource analysis must involve a diversity of static analysis, for escape, aliasing, algorithmic invariants, and more. Knowing this, we implement the Automated Amortized Resource Analysis framework (AARA) from scratch in our generic system. In this setting, access to resources is a state-passing effect which produces a compile-time approximation of runtime resource usage. We implemented type inference constraint generation for our calculus, accompanied with an elaboration of bounds for iterators on algebraic datatypes, for minimal ML-style programming languages with Call-by-Value and Call-By-Push-Value semantics. The closed-formed bounds are derived as multivariate polynomials over the integers. This now serves as a base for the development of an experimental toolkit for automated memory analysis of functional languages. Continued on ES/IODE ➡️ https://etcse.fr/TVbM ------- If you find this interesting, feel free to follow, comment and share. We need your help to enhance our visibility, so that our platform continues to serve you.

#Algorithms_Design_Techniques (Part-3) Classification by Design Approaches encompasses two main strategies for algorithm design: Top-Down Approach: This method involves breaking down a complex problem into smaller, more manageable sub-problems. The process continues recursively until each sub-problem is solvable, eventually leading to a solution for the original complex problem. Bottom-Up Approach: Conversely, the bottom-up approach, also known as the reverse of the top-down approach, involves solving individual components of a complex program using a programming language. These components are then combined to form the complete program. In the top-down approach, the system is designed starting from the highest level of abstraction and gradually refining it to lower levels, whereas the bottom-up approach builds the system by starting with individual components and integrating them into a larger system. Each approach has its own advantages and disadvantages, with the choice often dependent on the specific problem at hand. Additionally, algorithms can be classified into other categories, including: Randomized Algorithms: These algorithms utilize random choices to achieve faster solutions. An example is the Randomized Quicksort Algorithm. Classification by Complexity: Algorithms are categorized based on the time taken to solve a problem for a given input size, known as time complexity analysis. Some algorithms have linear time complexity (O(n)), while others have exponential time complexity. Classification by Research Area: Each field in computer science has its own set of problems that require efficient algorithms. Examples include Sorting Algorithms, Searching Algorithms, and Machine Learning algorithms. Branch and Bound Enumeration and Backtracking: These techniques are commonly used in Artificial Intelligence. In conclusion, the classification of algorithms plays a vital role in organizing, understanding, and comparing different algorithms. Whether categorized by design method, complexity, or research area, these classifications aid in problem-solving, performance comparison, and algorithm reuse. Moreover, they are essential for research and development in various fields of computer science, contributing to the efficiency and effectiveness of problem-solving processes.

🌟 14 Essential Algorithms Every Programmer Should Know 🌟 As a programmer, understanding key algorithms is crucial for solving complex problems efficiently. Here are 14 algorithms that form the backbone of computational thinking: Sorting Algorithms: e.g., Bubble Sort, Quick Sort, Merge Sort. Searching Algorithms: e.g., Binary Search, Linear Search. Graph Algorithms: e.g., Breadth-First Search (BFS), Depth-First Search (DFS). Dynamic Programming: Optimal substructure and overlapping subproblems. Greedy Algorithms: e.g., Dijkstra's algorithm, Prim's algorithm. String Algorithms: e.g., Knuth-Morris-Pratt (KMP) algorithm, Rabin-Karp algorithm. Tree Algorithms: e.g., Binary Tree traversal (inorder, preorder, postorder). Divide and Conquer: e.g., Binary Search, Merge Sort. Backtracking: e.g., N-Queens problem, Sudoku solver. Mathematical Algorithms: e.g., Euclidean algorithm (GCD), Sieve of Eratosthenes. Bit Manipulation: e.g., Bitwise operations, XOR properties. Sorting Network: e.g., Bitonic sort, Batcher's odd-even merge. Parallel Algorithms: e.g., Parallel merge sort, Parallel prefix sum. Randomized Algorithms: e.g., QuickSelect, Monte Carlo algorithms. Mastering these algorithms not only enhances problem-solving skills but also lays a strong foundation for algorithmic thinking in software development. Which algorithms have been most impactful in your programming journey? #Algorithms #Programming #SoftwareDevelopment #ProblemSolving #ComputerScience #ContinuousLearning

Exciting news! Our paper titled "Synthesizing Libraries of Programs with Auxiliary Functions" has been published in the Transactions on Machine Learning Research (TMLR). Check it out: https://lnkd.in/gwBSwtF2 #ProgramSynthesis #MachineLearning #Research #Programming #AI

Interesting paper: Programmable Variational Inference Paper link on Hugging Face: https://lnkd.in/gRnQ2WQC #paper #bookmark

🚀 Exploring #LoRA and Full Finetuning in Large Language Models 🧵👇 🔍 New Research from Columbia University & Databricks Mosaic AI! 1️⃣ Instruction Finetuning with 100K Prompt-Response Pairs - 🔹 Finding: Full finetuning outperforms LoRA in specialized tasks like programming and math. - 🔹 Insight: Full finetuning adapts better to specific tasks, while LoRA's regularization maintains broader task performance. 2️⃣ Continued Pretraining with 10B Unstructured Tokens - 🔹Finding: Full finetuning excels in target domains, LoRA retains base model capabilities in other tasks. - 🔹 Insight: Full finetuning’s adaptability leads to better target task performance, but LoRA preserves a wider skill set. 3️⃣ Regularization Effectiveness - 🔹 Finding: LoRA offers stronger regularization than weight decay and dropout. - 🔹 Insight: LoRA maintains performance across diverse tasks and generates more varied outputs. Great for general-purpose use! 4️⃣ Rank of Learned Perturbations - 🔹 Finding: Full finetuning learns perturbations with a rank 10-100x higher than typical LoRA configs. - 🔹 Insight: Higher rank explains full finetuning’s performance but comes with higher memory and computational costs. 5️⃣ Best Practices for Finetuning with LoRA - 🔹 Finding: Proposes strategies for balancing target task performance and broader model capabilities. - 🔹 Insight: Achieving a balance between specialization and generalization leverages LoRA’s regularization benefits. Conclusion - Full finetuning maximizes specific domain performance but at higher costs and risk of overfitting. - LoRA provides a balanced approach, maintaining broader capabilities with less computational power. Read the full paper here: 🔗 https://lnkd.in/dhMegFSZ

Some tech talk today! #technology 💪 The first phase of my coding project is stable - basic objects, user interface, and basic puzzle solving algorithm. I use a quite straightforward recursive algorithm https://lnkd.in/e-SDkt2B), which, I discovered later, is in a fact using backtracking https://lnkd.in/eymDuuAD. It works fine when there are about 10^4 options. It works horrible for the next problem, which is - my calculation may not be perfectly accurate, but I think the order of magnitude is OK - more in the 10^15 range! So I have to go into performance improvement, and this is another level of thrill... Here are a few tracks: - optimising the number or depth of branches to explore, with immediate exclusion tests ✔ - subdivision of the puzzle, when needed. Did not prove so effective.❌ - I read about backjumping, but have not yet managed to see how I could use the concept ❔ - Implementing more memory- and process-efficient code. Almost done, needs performance testing ➕ - I am thinking about implementing heuristic valuation methods to rank branches according to their probability of success. Still a concept. I wonder if neural networks could help. I think it will be the next sprint. Do you have suggestions? It is really interesting to see how rapidly you need to analyse a problem more in-depth once you have managed to set up the MVP! #computerprogramming #performance #trainyourbrain

🤖 Turing-Complete Transformers: Two Transformers are more Powerful than One. In this paper https://lnkd.in/d2sppTVK, currently under review as a conference paper at ICLR2023, the researchers present Find+Replace, a family of multi-transformer architectures that are Turing-complete. They also show that this architecture outperforms GPT-4 on a set of classical Computer Science problems, like the Hanoi towers or dynamic programming. Firstly, the authors prove that Transformers are not Turing-complete, as they have fixed length and fixed vocabulary sizes. Computations that can be done through a Transformer are limited. Their proposal is the Find+Replace architecture, a multi-transformer system that operates on a sequence of arbitrary length called tape (as Turing himself would have called it). The Find Transformer identify parts of the input that pass to the Replace Transformer, which performs what essentially performs a mapping function. This find-and-replace approach is equivalent to three lambda calculus reductions, which in the real world means that it behaves like a programming language, being capable of solving any problem. This is the proof that this approach is Turing-complete. Having a Transformer architecture equivalent to a programming language also has its own perks, like initialising non-random weights or faster convergence. With this approach, they were able to solve the Tower of Hanoi problems of any input size. GPT-3 couldn't solve any, GPT-4 only had a problem with size 3. Isn't that impressive? It's too early to tell the implications of this work, but at least it is a really interesting read, and at most, world-changing. #nlproc #llms #python #opensource

Turing-complete Transformers might just be as big a leap for AI as transformers were for language models. The Find+Replace beating GPT-4? That's huge. We could be looking at the biggest AI breakthrough this year. Scoring perfect on tests is self-explanatory, but what's mind-blowing is their claim that this new setup is Turing-complete. If you know a bit about theoretical computer science, you'll realize this is a massive deal. Not in the short term, but probably this can become the new standard architecture for future models. #LLM #AI #TuringComplete

🚀 Kadane's Algorithm: Your Key to Efficient Subarray Sum Calculation Ever wondered how to find the contiguous subarray within a list of numbers that gives the maximum sum? Meet Kadane's Algorithm, your solution for efficient computation! 📈 🔍 What does it do? Kadane's Algorithm is a clever technique that quickly pinpoints the subarray with the highest sum in a list of numbers. This problem-solving gem has wide applications, from finance to data analysis. 🛠️ How does it work? It's all about dynamic programming! This algorithm scans through the numbers, keeping tabs on the maximum sum seen so far and the maximum sum ending at each position in the list. ⚡ Why is it awesome? 1. Super Speedy:With a time complexity of O(n) for a list of 'n' numbers, it's lightning-fast compared to brute-force methods. 2. Space Saver: Plus, it does all this without gobbling up extra memory! 🌐 Where does it shine? Kadane's Algorithm pops up everywhere: - Crunching stock market data. - Analyzing images for contiguous areas. - Identifying sequences in genetics. - Powering up algorithms and machine learning for optimized calculations. 📚 Learning and Using It For anyone diving into algorithms or wanting to supercharge their problem-solving skills, Kadane's Algorithm is a must-know. Understanding it and putting it into practice can level up your computational game! 💡 Wrap Up Simple yet powerful, Kadane's Algorithm showcases the magic of elegant solutions in the world of computer science. Mastering it unlocks efficient ways to crack complex problems! #Algorithms #KadanesAlgorithm #Efficiency #Programming #ProblemSolving #ComputerScience